2020 카카오 인턴십 : 동굴 탐험(c++) / Tree+BFS

어떤 알고리즘으로 문제를 풀지를 고민하는 데 엄청 시간이 오래 걸렸다.

다른 분들의 풀이를 참고한 결과 bfs와 tree를 사용해서 푸는 문제였고

이전에 반드시 방문해야하는 방 => before

이전에 반드시 방문해야하는 방을 방문하지 않아 잠시 보류를 하는 방 => after

을 표시하여 적절하게 구현해주는 문제였다.

 

문제를 풀어도 30번 테케가 계속 틀려서 찾아보니

0번방은 반드시 이전에 방문해야하는 방이 존재하면 안된다는 조건을 걸어주어야 했다.

0번방이 start지점이기 때문에 before[0]!=0이라면 false를 리턴해주었다.

 

// 동굴탐험
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <iostream>
 
using namespace std;
 
vector<vector<int>> graph;
unordered_map<int, int> before;
unordered_map<int, int> after;
vector<bool> checked;
 
void bfs()
{
    queue<int> q;
    checked[0] = true;
    q.push(0);
    
    while(!q.empty()){
        int node = q.front();
        q.pop();
        
        
        for(int i=0; i<graph[node].size(); i++){
            int next = graph[node][i];
            if(checked[next]) continue;
            if(!checked[before[next]]){
                after[before[next]] = next;
                continue;
            }
            
            q.push(next);
            checked[next] = true;
            
            if(after.find(next) != after.end()){
                q.push(after[next]);
                checked[after[next]] = true;
            }
        }
    }
}
 
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    
    graph.resize(n);
    checked.resize(n);
    
    for(int i=0; i<path.size(); i++){
        graph[path[i][0]].push_back(path[i][1]);
        graph[path[i][1]].push_back(path[i][0]);
    }
    
    for(int i=0; i<order.size(); i++){
        before[order[i][1]] = order[i][0];
    }
    
    // 0번방 이전에 방문해야하는 곳이 있다면, 불가능하다.(왜냐면, 동굴의 입구는 반드시 0번방부터 출발해야하기 때문..)
    if(before[0]!=0) return false;
    
    bfs();
    
    for(int i=0; i<n; i++){
        if(!checked[i]){
            answer = false;
            break;
        }
    }
    
    return answer;
}