[프로그래머스] 동굴탐험

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

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

 

주의점

1. 문제에서 0번부터 시작한다고 알려준다. 루트를 찾을 필요가 없다.

2. 문제에는 안나와 있지만 order에 [1,0] 처럼 0번 노드의 선행조건이 있는 테스트 케이스가 있다고 한다. (59번 라인 예외처리)

 

풀이

1. 선행 됐어야 하는 노드가 있었나? -> 대기열(set)에 넣는다.

2. 해당 노드가 선행 됐어야 했던 노드였나? (큐에 해당 노드의 후행 노드가 있는가?) 

    -> 대기열(set)에서 빼서 진행열(queue)에 넣고 방문표시를 한다.

3. 위 2개에 해당사항이 없는 노드인가? -> 진행열(queue)에 넣으면서 해당 노드는 방문표시를 한다.

 

이렇게 하면 모든 정점을 방문한경우 visited 배열이 전부 true 로 되고

방문하지 못하는 경우는 대기열에 넣은 노드의 선행노드를 방문할 수 있는 경우가 전혀 없었다는 (문제의 3번예제) 것이기때문에 큐에 후행노드가 넣어지지 못해 while문이 종료되고 visited 배열이 전부 true가 되지 못한다.

(와 나 설명진짜 못하는것 같다... ㅠㅠ)

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
int N;
bool answer;
vector<int> tree[200001];
int visited[200001];
unordered_set<int> s;
int before[200001];
int after[200001];


// 선행조건이 있는 노드면 q에넣고 대기
// q에 있었던 노드면 빼서 방문하고 q에 넣는다 -> 이제 방문가능함. 계속 방문못하면 가는길 없는 거임

void bfs(int cur) {
    queue<int> q;
    q.push(cur);
    visited[cur]=1;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        before[after[cur]]=0; // 기본 루틴의 경우 추가해준 후행의 선행은 0으로 원복
        if(s.find(after[cur])!=s.end()){
            s.erase(after[cur]);
            visited[after[cur]]=1;
            q.push(after[cur]);
        }
        for (int i=0; i<tree[cur].size(); i++){
            int next = tree[cur][i];
            if(visited[next]) continue;

              // 선행조건이 있는 노드인가
            if(before[next]!=0){
                s.insert(next);
                continue;
            }
            // 선행조건이 없는 노드 였다.
            visited[next]=1;
            q.push(next);
        }
    }
}
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    answer = true;
    N=n;
    
    for (int i=0; i<path.size(); i++) {
        tree[path[i][0]].push_back(path[i][1]);
        tree[path[i][1]].push_back(path[i][0]);
    }
    for (int i=0; i<order.size(); i++) {
        after[order[i][0]] = order[i][1];
        before[order[i][1]] = order[i][0];
    }
    if(before[0]!=0) return false;
    bfs(0);
    for (int i=0; i<n; i++){
        if(visited[i]==0) answer = false;
    }
    return answer;
}