[Programmers] 2020 카카오 인턴십: 동굴 탐험(C++) / Topological Sort

programmers.co.kr/learn/courses/30/lessons/67260

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

풀어본 카카오 기출 문제 중 유일한 위상 정렬 문제

처음에는 방문하는 경로를 구하는 줄 알고 엄청나게 복잡하게 생각했으나 모든 node를 방문 가능/불가능만 구하면 되는 문제였어서 간단한 위상 정렬 알고리즘으로 풀 수 있었다

 

위의 그림과 같은 지도가 있고 (4->1), (6->7), (8->5)의 방문 순서를 지켜야 한다고 할 때 방문 순서에 대한 노드들의 관계는 다음으로 나타낼 수 있다

 

루트 노드는 0으로 고정되어 있고, 문제의 조건 중 "서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다."라는 부분이 명시되어 있기 때문에 그래프는 트리의 형태를 가진다.

왼쪽의 그림은 해당 노드를 방문하기 전에 먼저 들려야 하는 노드의 관계도를 나타낸 것이고, 그래프의 edge 관계를 reverse한 것이 오른쪽 그래프이다.

오른쪽 그래프에서 탐색을 시작하면 된다.

 

 

1. 입력받은 edge 배열은 방향성이 없기 때문에 우선은 무방향 그래프의 형태로 저장해준다.
2. 0번 노드에서 DFS 탐색을 시작한다(0번 노드가 루트 노드임이 고정되어 있기 때문). parent node를 가리키는 방향그래프가 아니라 child node를 가리키는 방향 그래프를 생성해야 한다
3. order 배열에 있는 추가 edge 정보를 이용해 방향 그래프에 추가해준다
4. topological sort를 수행해준다(방향 정보를 이용해 indegree를 우선 구해준다)

 

형광펜으로 칠해진 노드는 다음에 사라질 노드를 의미한다.

노드를 없애면서 해당 노드가 가리키고 있는 노드들의 indegree를 감소해주고, 다음 탐색에서는 indegree가 0인 노드에 대해 진행해주는 방식으로 topological sort를 구현했다.

이 떄 edge의 cycle이 형성된다는 것 -> 해당 cycle 내의 모든 node 내에 선수관계가 존재한다는 것 -> 위상 정렬을 수행해도 indegree가 0이 될 수 없음

을 의미하기 때문에 topological sort를 수행한 뒤에도 노드의 잔여 여부로 탐색 성공/실패를 결정해주었다.

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

void dfs(int cur, vector<vector<int>>& ug, vector<vector<int>>& og, vector<bool>& visit) {
    visit[cur] = true;

    for (auto x : ug[cur]) {
        if (!visit[x]) {
            og[cur].push_back(x);
            dfs(x, ug, og, visit);
        }
    }
}

bool toposort(int n, vector<vector<int>> og) {
    vector<int> indeg(n,0);

    for (int i = 0; i < n; i++)
        for (auto x : og[i])
            indeg[x]++;

    queue<int> q;
    q.push(0);
    int cnt=0;

    while (!q.empty()) {
        int cur = q.front(); q.pop(); cnt++;

        for (auto x : og[cur]) {
            if (!indeg[x])continue;

            if (--indeg[x] == 0)
                q.push(x);
        }
    }

    return cnt==n;
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    vector<vector<int>> ug(n), og(n);

    for (auto p : path) {	//무방향 그래프 생성
        ug[p[0]].push_back(p[1]);
        ug[p[1]].push_back(p[0]);
    }
    
    vector<bool> visit(n,false);
    dfs(0, ug, og, visit);	//0번 노드에서 dfs 탐색해서 방향 그래프를 생성

    for (auto o : order) {	//추가 order 배열에 의해 edge를 추가한다
        og[o[0]].push_back(o[1]);
    }

    return toposort(n,og);
}