[ 프로그래머스 - 동굴 탐험 ] 해설 및 코드

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

 

목적

두 방의 경로(path)와 순서(order)가 주어질 때, n개의 방을 모두 방문할 수 있는지 구하자.

 

접근법

• 트리 형태로 구성된 동굴을 0번 방 부터 dfs 방식으로 방문한다.
• 도중에 순서(order)로 인해 계속해서 아래로 갈 수 없는 방은 매달아 둔다. 그리고 가능한 시점에 방문을 계속한다. (아래 코드 참조)

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

const int MAXN=2e5;
bool vis[MAXN];
int prior[MAXN],hang[MAXN];
vector<int> edge[MAXN];

void visit(int v){
    if(vis[v])return;
    
    if(!vis[prior[v]]){		// 2
        hang[prior[v]]=v;
        return;
    }
 
    vis[v]=true;
    visit(hang[v]);		// 3
    for(int u:edge[v])visit(u);
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    // 1
    for(auto &a:path){
        edge[a[0]].push_back(a[1]);
        edge[a[1]].push_back(a[0]);
    }
    for(auto &a:order)prior[a[1]]=a[0];

    if(prior[0])return false;

    vis[0]=true;
    for(int u:edge[0])visit(u);
    
    for(int i=0;i<n;++i)if(!vis[i])return false;
    return true;
}

 

1. edge[i]에는 i번 방과 연결된 방들이 vector로 저장되어 있고, prior[i]는 i번 방 이전에 방문해야 하는 방 번호이다(default 0으로). 그리고 0번 방 이전에 방문해야 하는 방이 있는 경우 예외처리 한다. dfs는 0번 방에서 갈 수 있는 방들을 시작으로 진행한다.
2. 방문 조건이 맞는지 확인한다. v번 방 이전에 방문해야 하는 방을 아직 방문하지 않았다면 hang에 매달아 두고 리턴한다.
3. 전에 매달아 둔 방이 있다면 계속해서 dfs를 진행한다. 그리고 나서 일반적인 dfs 방식처럼 방문을 계속한다.

O(n)이라는 단순한 시간복잡도로 해결된다.

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.