[프로그래머스] 동굴 탐험(C++)

[문제]

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

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

 

[풀이]

 

특별한 알고리즘을 사용해서 해결해야되는 문제일줄 알았는데

내가 가장 많이 다루었던 DFS 알고리즘을 사용해 해결하는 문제라는게 놀라웠다.

 

한번 방문한 곳은 재방문 안해도 된다는 점에 있어서 이해가 안됐는데

모든 경로는 연결되어 있으므로 재방문을 고려하지 않아도 된다. 

[코드]

#include <string>
#include <vector>
#include <map>
#define MAX 200000

using namespace std;

vector<int> v[MAX];
int hang[MAX]={0,};
bool visited[MAX]={0,};
map <int,int> post;

void DFS(int idx)
{
    if(visited[idx])    return;
    if(post.find(idx) != post.end())
    {
        int pre = post.at(idx);
        if(!visited[pre])
        {
            hang[pre] = idx;
            return ;
        }
    }
    visited[idx]=true;
    DFS(hang[idx]);
    for(int i=0;i<v[idx].size();i++)    DFS(v[idx][i]);
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;

    for(auto tmp : path)
    {
        v[tmp[0]].push_back(tmp[1]);
        v[tmp[1]].push_back(tmp[0]);
    }
    
    for(auto tmp : order)    post.insert(make_pair(tmp[1], tmp[0]));
    
    if(post.find(0) != post.end() )   return false;
   
    visited[0]=true;
    for(int idx : v[0]) DFS(idx);
   
    for(int i=0;i<n;i++)    if(!visited[i]) answer= false;
    
    return answer;
}