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

문제 링크

dfs

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<int>> graph;  // 인접 리스트 (정점 별 연결된 정점)
unordered_map<int, int> reserve; // Key : 방 번호,  Value : 이 방 다음에 방문해야하는 예약된 방
unordered_map<int, int> before;  // Key : 방 번호,  Value : 이 방 전에 반드시 방문해야 하는 방
vector<bool> visited;  // 방문이 완료된 방

void DFS(int num) { // 현재 방문 방 : num
    if (!visited[before[num]]) { // 이전에 방문해야 하는 방이 아직 방문 상태가 아니라면 num 은 방문될 수 없으므로 돌아가야 한다. 
        reserve[before[num]] = num; // reserve[before[num]] 에 num 을 저장해두고 나중에 before[num] 을 방문하게 되면 그때 num 을 방문하자
        return;
    }

    visited[num] = true; // num 방문 완료 처리
    if (reserve[num] > 0) // num 이 아직 방문되지 않아 방문 못했었던 방이 있다면 (reserve[num > 0]) 그 방 DFS 방문하러 고고
        DFS(reserve[num]);
    for (int i = 0; i < graph[num].size(); ++i){ // num 과 연결된 다음 방들 DFS 순회
        int next = graph[num][i];
        if (!visited[next]) // 방문한적 없는 방에 대해서만 순회 가능
            DFS(next);  
    } 
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    
    // graph 채우기
    graph.resize(n);
    for (int i = 0; i < path.size(); ++i) {
        graph[path[i][0]].push_back(path[i][1]);
        graph[path[i][1]].push_back(path[i][0]);
    }

    // before 채우기
    for (int i = 0; i < order.size(); ++i)
        before[order[i][1]] = order[i][0];
    
    // 만약 0 보다 먼저 방문되야 하는 방이 있다고 order 에서 말하고 있다면 그건 잘못된 것이다. 0 부터 먼저 방문한다고 문제에서 말해주었기에!
    if (before[0] != 0) return false;

    visited.resize(n);
    visited[0] = true; // 0 번 방 방문처리
    // 0 번방과 연결된 방들에 대해 DFS
    for (int i = 0; i < graph[0].size(); ++i)
        DFS(graph[0][i]);

    // DFS 순회를 전부 끝낸 후, 방문 안된 방이 하나라도 있으면 answer = false
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            answer = false;
            break;
        }
    }

    return answer;
}

bfs

#include <string>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

vector<vector<int>> graph;
unordered_map<int, int> reserve;
unordered_map<int, int> before;
vector<bool> checked; // 방 별로 큐에 삽입된 적이 있는지

void BFS() {
    queue<int> q;
    checked[0] = true;
    q.push(0); // 0 번 방부터 시작

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        for (int i = 0; i < graph[now].size(); ++i) {
            int next = graph[now][i];
            if (checked[next]) continue; // 이미 큐에 삽입된적 있는 방이면 X
            if (!checked[before[next]]) { // 이 방 전에 먼저 예약 되야할 방이 아직 예약되지 않은 상태라면 X
                reserve[before[next]] = next;
                continue;
            }
            // 1. next 예약
            q.push(next);
            checked[next] = true;
            // 2. next 가 예약되지 않아 예약되지 못하고 있었던 방 예약
            if (reserve.find(next) != reserve.end()) {
                q.push(reserve[next]);
                checked[reserve[next]] = true;
            }
        }
    }
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;
    
    graph.resize(n);
    for (int i = 0; i < path.size(); ++i) {
        graph[path[i][0]].push_back(path[i][1]);
        graph[path[i][1]].push_back(path[i][0]);
    }

    for (int i = 0; i < order.size(); ++i)
        before[order[i][1]] = order[i][0];

    if (before[0] != 0) return false;

    checked.resize(n);
    BFS();

    for (int i = 0; i < n; ++i) {
        if (!checked[i]) {
            answer = false;
            break;
        }
    }

    return answer;
}