프로그래머스 문제 - 동굴 탐험

프로그래머스 동굴 탐험 문제 풀이를 진행하였습니다.

문제 정보

문제 풀이

트리처럼 이어진 동굴을 전부 탐색 가능한지 확인하는 문제입니다.
추가적으로 동굴을 탐색하기 전 먼저 탐색을 해야하는 방이 존재할 수 있습니다.

일단 동굴을 노드라고 생각했을 때 양방향으로 이동이 가능하도록 간선을 연결해줍니다.
그리고 특정 동굴을 탐색해야 갈 수 있는 동굴들을 key와 lock배열로 나누어 저장해줍니다.

만약 탐색을 하다가 가면 안되는 동굴이 나오더라도 나중에 bfs를 통해 key에 접근하여 그 동굴에 접근할 수 있게 된다.
즉, 가면 안되는 동굴이 나오면 그 동굴을 따로 저장해두었다가 갈 수 있는 key에 접근 시 저장해둔 동굴도 함께 탐색을 시작하면 된다.
이러면 한번 간 길을 다시 갈 필요가 없고, 따로 길을 저장해줄 컨테이너만 만들어두면 한 번의 탐색만으로 모든 동굴을 탐험 가능한지 알 수 있다.

여기서 반례는 생각하지 못했지만, order에 0이 추가되는 경우의 수가 존재합니다.
임의의 동굴을 통과해야 0번 동굴을 갈 수 있다면 그 동굴은 탐험이 불가능한 동굴이 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    vector<int> cave[n];
    vector<bool> visited(n, false);
    
    //간선 연결
    for(vector<int> v : path)
    {
        cave[v[0]].push_back(v[1]);
        cave[v[1]].push_back(v[0]);
    }
    
    //선 방문 동굴 설정
    vector<int> key(n, 0);
    vector<int> lock(n, 0);
    for(vector<int> v : order)
    {
        key[v[0]] = v[1];
        lock[v[1]] = v[0];
    }
    
    vector<int> visitedLock(n, 0);
    queue<int> q;
    if(lock[0] != 0)    //0번 방이 어느 동굴을 탐색해야 갈 수 있다면 탐험 불가능
        return false;
    
    q.push(0);
    while(!q.empty())
    {
        int qSize = q.size();
        for(int i = 0; i < qSize; i++)
        {
            int cur = q.front();    q.pop();
            visited[cur] = true;
            for(int num : cave[cur])
            {
                if(visited[num])
                    continue;
                
                if(lock[num] != 0)    //먼저 탐색해야 하는 동굴인 경우
                {
                    visitedLock[num] = 1;
                }else
                {
                    q.push(num);
                    if(key[num] != 0) //현재 방문한 동굴이 정해진 동굴일 경우
                    {
                        lock[key[num]] = 0;

                        if(visitedLock[key[num]] != 0)  //정해진 동굴을 방문하여 갈 수 있는 동굴에 탐색을 진행한 경우
                        {
                            q.push(key[num]);
                            visitedLock[key[num]] = 0;
                        }
                    }
                }
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        if(!visited[i])
            return false;
    }
    
    return answer;
}

출저

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