문제 설명

오지 탐험가인 프로도는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. 임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다.

탐험에 앞서 이 지하 동굴의 지도를 손에 넣은 프로도는 다음과 같이 탐험 계획을 세웠습니다.

모든 방을 적어도 한 번은 방문해야 합니다.
특정 방은 방문하기 전에 반드시 먼저 방문할 방이 정해져 있습니다.
- 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다.
- 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다.
- 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다.
- 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다.

위 계획 중 2-2, 2-3, 2-4는 순서를 지켜 방문해야 하는 두 방의 쌍이 A → B(A를 먼저 방문하고 B를 방문함) 형태로 유일함을 의미합니다. 즉, 프로도는 아래와 같은 형태로 방문순서가 잡히지 않도록 방문 계획을 세웠습니다.

A → B, A → C (방문순서 배열 order = […,[A,B],…,[A,C],…]) 형태로 A를 방문 후에 방문해야 할 방이 B와 C로 두 개 또는 그 이상인 경우 X → A, Z → A (방문순서 배열 order = […,[X,A],…,[Z,A],…]) 형태로 A를 방문하기 전에 방문해야 할 방이 X와 Z로 두 개 또는 그 이상인 경우 A → B → C (방문순서 배열 order = […,[A,B],…,[B,C],…) 형태로 B처럼 A 방문 후이면서 동시에 C 방문 전인 경우 그리고 먼저 방문해야 할 방과 나중에 방문할 방을 반드시 연속해서 방문해야 할 필요는 없어 A방을 방문한 후 다른 방을 방문한 후 B방을 방문해도 좋습니다.

방 개수 n, 동굴의 각 통로들이 연결하는 두 방의 번호가 담긴 2차원 배열 path, 프로도가 정한 방문 순서가 담긴 2차원 배열 order가 매개변수로 주어질 때, 프로도가 규칙에 맞게 모든 방을 탐험할 수 있을 지 return 하도록 solution 함수를 완성해주세요.

제한사항

n은 2 이상 200,000 이하입니다.
path 배열의 세로(행) 길이는 n - 1 입니다.
- path 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
- 두 방 A, B사이를 연결하는 통로를 나타냅니다.
- 통로가 연결하는 두 방 번호가 순서없이 들어있음에 주의하세요.
order 배열의 세로(행) 길이는 1 이상 (n / 2) 이하입니다.
- order 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
- A번 방을 먼저 방문한 후 B번 방을 방문해야 함을 나타냅니다.

풀이

2020 카카오 인턴십 코딩테스트 마지막 문제로, 알고리즘 지식과 더불어 응용력이 필요한 문제였습니다.

문제를 읽는 과정에서 다음과 같은 문장을 통해 문제 유형을 유추할 수 있습니다.

특정 방은 방문하기 전에 반드시 먼저 방문할 방이 정해져 있습니다

네, 바로 위상정렬입니다. 특정 노드에 방문하기 전에 반드시 방문해야 할 노드가 주어진 경우, 이에 맞게 정렬을 수행하는 알고리즘 입니다.

위상정렬이 가능하려면 한 가지 조건을 만족해야 합니다. 바로 정렬하려는 그래프가 DAG(Directed Acyclic Graph)여야 한다는 점입니다. 번역하면 방향성 비순환 그래프로, 단방향이면서 사이클이 존재하지 않는 그래프를 뜻합니다. 따라서 본 문제에서 주어진 그래프가 DAG인지 확인하는 것은 위상정렬이 가능한지에 대한 판단이고, 이것은 즉 모든 노드를 방문 가능한지를 판단하는 것과 같습니다.

그런데 하나의 그래프에서 위상정렬 알고리즘을 수행하려면 우선 그래프가 단방향 그래프여야 합니다. 그래프에 사이클이 있는 경우는 위상정렬 알고리즘을 수행하는 과정에서 그래프가 DAG가 아님을 판단할 수 있지만, 그래프가 양방향일 경우 위상정렬 알고리즘을 수행할 수조차 없습니다. 따라서 본 문제는 주어진 그래프를 단방향 그래프로 변환한 후 위상정렬 알고리즘을 수행하는 것으로 해법을 정리할 수 있습니다.

단방향 그래프로의 변환 과정은 그래프 탐색을 통해 모든 두 쌍의 노드에 대해서 같은 한 방향으로만 연결시켜준 뒤에 order 배열로 주어진 특수 노드 쌍들을 반영해주면 됩니다.

위상정렬의 경우 DFS와 BFS를 이용한 두 가지 방법이 있습니다. 위상정렬의 결과를 출력할 경우에는 둘 다 O(N)의 시간복잡도를 갖지만, 위상정렬이 가능한지에 대한 판단은 DFS의 경우 모든 노드 쌍에 대하여 역간선이 존재하는지를 확인하기 때문에 O(N^2)의 시간복잡도를 갖습니다. 반면 BFS의 경우 모든 노드를 방문하기 전에 큐가 비는 경우를 찾으면 되므로 O(N)만에 판단할 수 있습니다. 따라서 시간 초과를 면하기 위해선 BFS를 이용한 위상정렬 알고리즘을 사용해야 합니다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

int indegree[200000];
vector<int> adj[200000];

// 단방향 그래프 변환
void buildUnidirGraph(int n, vector<vector<int>>& path, vector<vector<int>>& order) {
    queue<int> q;
    vector<bool> check(n);
    vector<vector<int>> paths(n);
    
    for(auto v : path) {
        paths[v[0]].push_back(v[1]);
        paths[v[1]].push_back(v[0]);
    }

    q.push(0);
    check[0] = true;
    
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for(int next : paths[cur])
            if(!check[next]) {
                adj[cur].push_back(next);
                ++indegree[next];
                q.push(next);
                check[next] = true;
            }
    }
    
    for(auto v : order) {
        adj[v[0]].push_back(v[1]);
        ++indegree[v[1]];
    }
}

// 위상정렬 - BFS
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    buildUnidirGraph(n, path, order);
    
    queue<int> q;
    
    for(int i = 0; i < n; i++)
        if(indegree[i] == 0)
            q.push(i);
    
    for(int i = 0; i < n; i++) {
        if(q.empty()) return false;
        
        int cur = q.front(); q.pop();
        for(int next : adj[cur])
            if(--indegree[next] == 0)
                q.push(next);
    }
    
    return true;
}

Android Developer

[프로그래머스] 동굴 탐험 풀이 (2020 카카오 인턴십)

문제 설명

제한사항

풀이

전체 코드