[프로그래머스][level4] [카카오 인턴] 동굴 탐험 (C++)

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

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

 

 

[난이도] level4
[유형] 그래프

[풀이]
우선 주어진 path로 인접 리스트를 만들었습니다. 풀이 중 필요없는 간선은 지워줄 것이기 때문에
vector가 아닌 set을 이용하였습니다.

order를 이용해 각 노드를 방문하려면 어떤 노드를 먼저 방문해야 하는지를 par 배열에 저장하였습니다.

풀이는 아래와 같습니다.

root부터 dfs를 돌리며 방문할 수 있는 노드 i를 방문하고 visit[i]=true 체크를 해줍니다.
방문할 수 없는 노드는 먼저 방문해야 하는 노드가 아직 방문하지 않은 상태로, visit[par[i]]==false인 상태입니다.
이 경우는 방문을 하지 않고 false를 return 해줍니다.

만약 모든 자식 노드들의 dfs 함수가 true를 return 했다면 모든 자식을 방문한 것이므로 현재 노드는 더이상 확인할 필요가 없습니다. 그러므로 인접 리스트로 사용되는 set에서 현재 노드와 부모 노드의 간선을 끊어줍니다.
위 제거 과정을 해주지 않으면 반복되는 dfs에 의해 시간 초과가 발생합니다.

이렇게 한 시행을 완료하였으면 새롭게 visit된 노드의 개수를 total에 더해줍니다.
만약 새롭게 visit된 노드가 있다면 이 노드가 visit되지 않아 이전 시행에서 방문하지 못했던 노드들도 이제 방문이 가능해진 것이기 때문에 다시 root부터 dfs를 돌리며 같은 시행을 반복합니다.

만약 visit된 노드 개수가 0이라면 더 이상 방문이 불가능하여 모든 노드를 방문할 수 없는 상태이므로 최종답으로 false를 return 합니다.

모든 노드를 방문해서 total==n 이 된다면 최종답으로 true를 return 해주면 됩니다.

#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
bool visit[200001];
set<int> adj[200001];
int par[200001],cnt,total;
bool sol(int prv, int n){
    if(par[n]!=-1 && !visit[par[n]]) return 0;
    if(!visit[n]) cnt++;
    visit[n]=1;
    bool ret=1;
    for(int nxt : adj[n]){
        if(nxt!=prv && !sol(n,nxt)) ret=0;
    }
    if(ret && n!=0) {
        adj[prv].erase(n);
        adj[n].erase(prv);
    }
    return ret;
}
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    memset(par,-1,sizeof(par));
    for(auto& p : path) adj[p[0]].insert(p[1]), adj[p[1]].insert(p[0]);
    for(auto& o : order) par[o[1]]=o[0];
    while(1){
        cnt=0;
        sol(-1,0);
        if(cnt==0) return 0;
        total+=cnt;
        if(total==n) return 1;
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/[카카오_인턴]_동굴_탐험.cpp

 

 

 

※ 아래 링크의 카카오에서 제공하는 공식 풀이는 방향 그래프의 cycle 판별을 이용한 풀이입니다.
https://tech.kakao.com/2020/07/01/2020-internship-test/

cycle을 활용한 풀이 코드는 아래와 같습니다.

#include <vector>
using namespace std;
bool visit[200001],finished[200001];
vector<int> tadj[200001],adj[200001];
void dfs(int prv,int n){
    for(auto nxt : tadj[n]){
        if(prv!=nxt) {
            adj[nxt].push_back(n);
            dfs(n,nxt);
        }
    }
}
bool dfs2(int n){
    visit[n]=1;
    for(auto nxt : adj[n]){
        if(!visit[nxt]){
            if(!dfs2(nxt)) return 0;
        }else if(!finished[nxt]) return 0;
    }
    finished[n]=1;
    return 1;
}
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    for(auto& p : path) tadj[p[0]].push_back(p[1]), tadj[p[1]].push_back(p[0]);
    dfs(-1,0);
    for(auto& o : order) adj[o[1]].push_back(o[0]);
    for(int i=0;i<n;i++) if(!visit[i] && !dfs2(i)) return 0;
    return 1;
}