[2020 카카오 인턴십] 동굴 탐험

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

프로그래머스

 

프로그래머스 플랫폼에 다시 적응할 겸, 간간히 프로그래머스도 풀려고 하는 중!

옛날에는 프로그래머스 3Lv도 엄청 어렵다 싶었는데, 또 풀만 한 것 같기도 하고...

대충 백준 골드? 1, 2, 3?? 모르겠다.

 

tc 하나가 pass가 안돼서 좀 걸렸다. ㅜㅜ

 

문제에서 방문 순서 조건을 A->B 유일로 주었기 때문에

아직 방문할 수 없는 노드를 탐색하게 되면 맵에 저장해 둔다. 그 외의 경우는 정상적으로 방문한다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
int isYet[200001];
int isVisited[200001];
vector<int> graph[200001];
queue<int> q;
unordered_map<int, int> m;
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    memset(isYet, -1, sizeof(isYet));
    for(int i = 0; i < order.size(); ++i)
    {
        int a = order[i][0];
        int b = order[i][1];
        isYet[b] = a;
    }
    for(int i = 0; i < path.size(); ++i)
    {
        int a = path[i][0];
        int b = path[i][1];
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    q.push(0);
    isVisited[0] = 1;
    if(isYet[0] != -1) return false;
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        for(int k = 0; k < graph[now].size(); ++k)
        {
            int nxt = graph[now][k];
            if(isVisited[nxt]) continue;
            if(isYet[nxt] == -1){
                q.push(nxt);
                isVisited[nxt] = 1;
            }
            else{
                if(isVisited[isYet[nxt]]){
                    q.push(nxt);
                    isVisited[nxt] = 1;
                    isYet[nxt] = -1;
                }
                else{
                    m[isYet[nxt]] = nxt;
                    isVisited[nxt] = 1;
                }
            }
        }
        if(m.find(now) != m.end())
        {
            q.push(m[now]);
        }
    }
    
    for(int i = 0; i < n; ++i)
    {
        if(isVisited[i]) continue;
        return false;
    }
    return true;
}