[프로그래머스] 동굴 탐험

동굴 탐험

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

풀이)

처음에 

dfs(방 탐색시 이용), before[]배열(이전에 꼭 방문해야하는 방 번호 저장), parent[]배열(트리 상에서 자식보다 먼저 방문해야하는 방 번호 저장) 을 이용해서 풀어보았지만 효율성면에서 떨어져서 다르게 풀어야했다.

효율성을 통과하지 못한 코드)

#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <iostream>
using namespace std;
vector <int> adj[200001];
int before[200001];
bool visited[200001];
int parent[200001];
int cnt = 0;
 
void get_parent(int here) { //트리상에서 부모번호를 저장하는 함수
 
    for (int i = 0; i < adj[here].size(); i++) {
        int next = adj[here][i];
        if (parent[next] == -1) {
            parent[next] = here;
            get_parent(next);
        }
    }
}
void dfs(int here) { //다음 정점을 방문처리하는 함수 
    visited[here] = true;;
    cnt++;
    for (int i = 0; i < adj[here].size(); i++) {
        int next = adj[here][i];
        if (visited[next] || !visited[before[next]]) continue;
        dfs(next);
 
    }
}
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    int a, b;
    for (int i = 0; i < path.size(); i++) {
        a = path[i][0];
        b = path[i][1];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 0; i < order.size(); i++) {
        a = order[i][0];
        b = order[i][1];
        before[b] = a;
    }
   if(before[0] != 0) return false;
    memset(parent, -1, sizeof(parent));
    parent[0] = 0;
    get_parent(0);
    dfs(0);
    int result_cnt = cnt;
    while (true) {
        cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && visited[before[i]] && visited[parent[i]]) {
                dfs(i);
            }
        }
        if (cnt == 0) break;
        result_cnt += cnt;
    }
    if (result_cnt == n) answer = true;
    else answer = false;
 
    return answer;
}

그래서 bfs 방법을 사용하고 before[]배열과 after[]배열(다음에 방문해야하는 방 번호)을 사용해줬다.

효율성 통과한 코드)

#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <iostream>
using namespace std;
vector <int> adj[200001];
int before[200001];
bool visited[200001];
int after[200001];
 
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    int a,b;
    for(int i=0;i<path.size();i++){
        a = path[i][0];
        b = path[i][1];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=0;i<order.size();i++){
        a = order[i][0];
        b = order[i][1];
        before[b] = a;
    }
    if(before[0] != 0) return false;
 
    queue<int> qu;
    visited[0] = true;
     for(int i=0;i<adj[0].size();i++){
            qu.push(adj[0][i]);
     }
 
    while(!qu.empty()){
        int here = qu.front();
        qu.pop();
        if(visited[here]) continue;
        if(!visited[before[here]]){//이전에 들려어야하는 곳을 아직 방문 안했다면
            after[before[here]] = here;
            continue;
        }   
        //cout << here << "-> ";
        visited[here] = true;
        for(int i=0;i<adj[here].size();i++){
            int next = adj[here][i];
            qu.push(next);
        }
        qu.push(after[here]);
    }
    for(int i=0;i<n;i++){
        if(!visited[i]){
            answer = false;
            break;
        }
    }
 
    return answer;
}

참고사항

자꾸 테스트케이스 30번 틀리는 경우!

-> 동굴을 들어가는 입구는 0번 방과 연결되어 있어서, 시작은 무조건 0번 방부터 해야하나

    order배열 중에 0번 방으로 입장 전에 다른 방 번호를 먼저 방문해야한다는 케이스가 들어있을 수 있다.

    이때는 바로 false를 return 해주도록 한다.