동굴 탐험

프로그래머스는 원래 레벨 2 ~ 3 문제 밖에 안푸는데 왜인지 모르게 오늘은 레벨 4의 문제를 읽고 꽤 풀만하다고 생각해서 도전해봤다. 사실 문제를 어떻게 풀지 계속 고민하느라 시간을 꽤 많이 사용하긴 했고 머리 속에 구현방법은 떠올랐으나 구현을 옮길려니 도저히 실행이 안되서 답을 참고했다. 내가 고민했던 부분을 참고했던 답에서는 쉽게 해결했어서 좀 허탈하기도 했다.

먼저 이 문제는 DFS 혹은 BFS로도 푸는게 가능하고 조금은 어려운 구현 아이디어를 집어넣어야한다. 특정 동굴은 다른 동굴을 먼저 방문 하지 않는다면 방문하는게 불가능하다. 그리고 우리는 이 특정 동굴을 발견했을때 끝나는게 아니고 미래에 필요한 동굴을 발견하고 재차 방문 할 수 있기 때문에 필요한 "예약" 의 느낌으로 DFS 탐색을 진행 해야 한다.

내가 고민했던거는 0 -> 1 로 갔을때 1은 특정동굴이니 다시 0을 호출하게 되었을때 다시 1을 방문하는것을 어떻게 막을 수 있을까 고민했는데 그냥 모든 동굴이 0이랑 이어진 특징을 살려서 0번째 동굴과 이어진 모든 동굴을 탐색하면 됐었다. map 을 활용하는것도 머리속에서 생각하고 있었고 특정 동굴을 방문하기 위해 필요한 동굴을 등록하고 -> 필요한 동굴을 발견했을때 특정동굴을 다시 방문하는 과정을 계속 거치다보면은 통과 할 수 있을것이다.

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

map<int,int> mustVisit; 
map<int, int> needVisit; 
vector<bool> visited; 

void dfs(int node, vector<vector<int>>& adj){
    
    if(!visited[mustVisit[node]]){
        needVisit[mustVisit[node]] = node;
        return; 
    }
    
    visited[node] = true; 
    if(needVisit.count(node)){
        dfs(needVisit[node],adj); 
    }
    for(int n : adj[node]){
        if(!visited[n]){
            dfs(n,adj); 
        }
    }
    
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    vector<vector<int>> adj(n); 
    for(vector<int>& v : path){
        adj[v[0]].push_back(v[1]); 
        adj[v[1]].push_back(v[0]); 
    }
    
    for(vector<int>& v : order){
        mustVisit[v[1]] = v[0]; 
    }
    
    if(mustVisit[0] != 0) return false; 
    
    visited.resize(n); 
    visited[0] = true; 
    for(int n : adj[0]){
        dfs(n,adj); 
    }
    
    for(int i = 0; i < visited.size(); i++){
        if(!visited[i]) return false; 
    }
    
    return answer;
}