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

처음에 문제를 봤을 때, 선수과목 문제처럼 일의 순서가 존재할 때 순서에 맞게 정렬하는 문제해결법인 '위상정렬'이 가장 먼저 떠올랐다. 때문에 그래프를 생성하고 순서에 대한 정보를 같이 저장해주면서 해당 node 보다 먼저 방문해야하는 수를 indegree에 저장해주었다. 실제로 문제상 indegree는 1이상의 값을 가질 수 없지만, 일반적으로 다 적용할 수 있게 하고 싶어서 나머지 부분도 맞춰서 코딩해주었다. 처음 시작점인 0을 queue에 넣어주고 graph에 저장된 값을 이용하여 연결되어 갈 수 있는 node를 찾아 queue에 다시 집어넣는다. queue에 들어갈 수 있는 node는 우선 방문 조건이 없는 node로 즉, 해당 node의 indegree값이 0이면 queue에 넣는다. queue에 값이 존재할 떄 까지 반복문을 돌고, queue에서 pop이 되는 순간 해당 node에 연결된 정보들을 업데이트한다. 만약 pop된 node가 우선 방문했었어야하는 node였다면, 다음 방문할 수 있는 node를 고르고 해당 node에 근접한 node 중에 이미 방문한 node가 있다면 방문할 수 있으므로 해당 node 또한 queue에 넣어준다.

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

using namespace std;

vector<vector<pair<int,int>>> graph;
// graph nxn-sized 2d vector of having two elements; the former is flag of whether i and j is connected, and the latter is # of indegree.
vector<bool> isvisited;
vector<int> indegree; 

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    graph.assign(n, vector<pair<int,int>>(n, {0,0}));
    isvisited.assign(n, false);
    indegree.assign(n, 0);
    
    /* make graph */
    for (auto p: path) {
        int v1 = p[0]; int v2 = p[1];
        graph[v1][v2].first = 1;
        graph[v2][v1].first = 1;
    }
    
    /* calculate # of indegree */
    for (auto o: order) {
        int prerequisite = o[0];
        int next = o[1];
        
        if (next == 0) return false;
        graph[prerequisite][next].second++;
        indegree[next]++;
    }
    
    queue<int> q;
    q.push(0);
    
    while (q.size()) {
        int from = q.front();
        isvisited[from] = true;
        q.pop();

        for (int i = 0; i < n; i++) {
            if (graph[from][i].second) {  // indegree-- cuz the prerequisite is deleted
                graph[from][i].second--;
                indegree[i]--;
                // printf("(%d,%d)\n", from, i);
                for (int j = 0; j < n; j++) {
                    if (isvisited[j] && graph[j][i].first) {
                        q.push(i);
                        break;
                    }
                }
                break;
            }
        }
        for (int to = 0; to < n; to++) {            
            if(graph[from][to].first && isvisited[to]==0) {  // there is a connection & never visit
                if (indegree[to] == 0) { // there is no prerequisite; therefore, it can be deleted.
                    q.push(to);
                    
                }
            }
        }
    }
    
    for (auto i: isvisited) {
        if (i == false) return false; 
    }
    return true;
}

정답은 맞았지만, 효율성에서 빵점이다. 쓸데없이 일반적으로 푼답시고 for문을 두 번 돌린 탓인 것 같았다. 문제상으로는 한 node를 방문하기 위해서 필요한 node는 한 개 이상 존재하지 않으므로, 일차원 벡터에 node의 앞뒤 순서 정보를 다 저장해주었다.(before[i]는 node i를 방문하기 위해 필요한 node 번호, after[i]는 node i를 방문 후 방문할 수 있는 node 번호) 앞선 코드에서는 방문 가능성을 근접한 node 중에 방문한 node가 있는 지를 확인했다면, 이미 방문했지만 선 방문해야하는 node가 있어 queue에 들어가지 못한 node를 표시해주었다. pop 시 만약 다음으로 갈 수 있는 node(after[now])가 이미 방문했던 node라면 이제는 방문할 수 있으므로 바로 queue에 넣어주었다. 추가로, graph또한 nxn이 아닌 다음으로 갈 수 있는 node정보만 저장하도록 변경하였다. 

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

using namespace std;

vector<vector<int>> graph;
vector<bool> isvisited;
vector<bool> isexist;
vector<int> before; 
vector<int> after;


bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    graph.assign(n, {});
    isvisited.assign(n, false);
    isexist.assign(n, true);
    before.assign(n, -1);
    after.assign(n, -1);
    
    /* graph[i] is a vector having connected node info. */
    for (auto p: path) {
        int v1 = p[0]; int v2 = p[1];
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }
    
    for (auto o: order) {
        before[o[1]] = o[0];
        after[o[0]] = o[1];
        if (o[1] == 0) return false;
    }
    
    queue<int> q;
    q.push(0);
    
    while(q.size()) {
        int now = q.front();
        isexist[now] = false;
        q.pop();
        
        if(after[now] != -1) {
            before[after[now]] = -1;
            if (isvisited[after[now]]) {
                q.push(after[now]);
            }
        }
        
        for (int i = 0; i < graph[now].size(); i++) {
            int next = graph[now][i];
            if (!isexist[next]) continue;  // is already deleted
            
            isvisited[next] = true;
            if (before[next] == -1) {  // no prerequisite
                q.push(next);
            }
            
        }
    }
    for (auto i: isexist) {
        if (i == true) return false;
    }
    return true;
}