[프로그래머스][2020 카카오 인턴십][C++] 동굴 탐험

문제

프로그래머스 2020 카카오 인턴십 - 동굴 탐험 (Level 4)

코딩테스트 연습 - 동굴 탐험

 

---

문제 풀이

접근 방식

프로도가 정한 방문 순서 규칙에 맞게 모든 방을 탐험할 수 있는지를 구하는 문제이다.

이 문제는 이해하기가 너무 어려워서 '질문하기'에 있는 풀이를 참고하여 문제를 해결하였다.

프로그래머스

 

위의 풀이에 따르면 방문 순서 규칙을 따르기 위해서는 사이클이 없는 그래프이어야 한다.

사이클이 존재한다면, 먼저 방문해야 하는 방을 가기 위해서

나중에 가야 하는 방을 먼저 방문해야만 하는 모순이 발생하기 때문이다.

 

그래서 사이클 여부를 확인하기 위해 path를 이용하여 양방향 그래프를 만들어 주었고,

0에서 이동을 시작하기 때문에 0에서 자식 노드로 가는 단방향 그래프를 만들어주었다.

단방향 그래프를 만들 때에는 BFS 방식으로 만들어주었다.

또한, 단방향 그래프에 방문 순서 규칙인 order도 추가해주었다.

(이를 추가해주고 DFS 탐색을 수행해야 방문 순서 규칙대로 탐색이 가능한지를 판단할 수 있다.)

이때, order 벡터에서 나중에 방문하는 방의 인덱스가 0인 경우에는 무조건 불가능한 경우이기 때문에,

이 경우에는 바로 false를 리턴해주었다.

 

단방향 그래프를 생성한 후, visit와 finish벡터, DFS 함수를 활용하여

0에서부터 탐색을 시작하여 단방향 그래프에 사이클이 존재하는지를 확인해주었다.

 

DFS 함수를 수행하며 visit 벡터에는 해당 방을 방문할 때마다 true를 저장하였고,탐색을 끝낸 방은 사이클이 존재하지 않는다는 의미로  finish에  true를 저장해주었다.그래서 다음으로 가야 할 방이 아직 방문하지 않았던 방이면 DFS를 재귀적으로 수행해주었고,이미 방문했던 방인데 탐색이 종료된 방이 아닌 경우에는 사이클이 존재한다는 의미이기 때문에 answer를 false로 만들고 DFS함수를 종료해주는 방식으로 구현하였다.

 

---

풀이 코드 - C++

#include <vector>
#include <queue>
using namespace std;

vector<int> bi_graph[200000];
vector<int> uni_graph[200000];
vector<bool> visit;
vector<bool> finish;
bool answer = true;

void DFS(int start) {
    if(answer == false)
        return;
    
    visit[start] = 1;
    for(auto next : uni_graph[start]) {
        if(visit[next] == 0)
            DFS(next);
        else if(finish[next] == 0){
            answer = false;
            return;
        }
    }
    finish[start] = 1;
    return;
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    // 양방향 그래프
    for(auto p : path) {
        bi_graph[p[0]].push_back(p[1]);
        bi_graph[p[1]].push_back(p[0]);
    }
    
    // 단방향 그래프
    queue<int> q;
    q.push(0);
    visit.assign(n, 0);
    visit[0] = 1;
    while(!q.empty()) {
        int now = q.front(); q.pop();
        for(auto t : bi_graph[now]){
            if(visit[t] != 0) continue;
            visit[t] = 1;
            uni_graph[now].push_back(t);
            q.push(t);
        }
    }
    for(auto o : order){
        if(o[1] == 0) return false;
        uni_graph[o[0]].push_back(o[1]);
    }
    
    // 사이클 존재 유무 판단
    visit.assign(n, 0);    
    finish.assign(n, 0);
    DFS(0);
    
    return answer;
}

실행 결과

실행 결과 : 100.0