[C++로 풀이] 동굴 탐험 (DFS, BFS) ⭐⭐⭐⭐

📌 동굴 탐험

난이도 ⭐⭐⭐⭐

🚀 문제

🚀 내 풀이

어떻게 접근해야할지 모르겠어서 어떻게 풀이하면 되는지를 구글링 해 보았는데 생각보다 풀이가 직관적이였다.. 그냥 DFS 혹은 BFS 로 순회를 하되 그 전에 방문을 마쳐야 할 노드가 있다면 방문 하지 않고 예약만 해둔 후, 전에 방문해야할 그 노드가 방문하면 그제서야 예약해두었던 노드를 방문하면 되는 것이였다. 좀 더 고민해볼걸 그랬다.

나는 입력 크기가 크면 DFS 는 어렵겠구나하고 기계적으로 생각하는 버릇이 있는데.. 이미 방문한 노드를 다시 재방문만 하지 않는다면 딱 노드 개수만큼의 시간복잡도를 이룰 수 있다. 시간 복잡도에 대해서 고민을 더 많이 해보아야겠다.😉

🔥 DFS 풀이 ⭕

order [[8, 5], [6, 7], [4, 1]] 인 경우의 DFS 순회 순서

• 최종 방문순서 👉 0, 3, 6, 7, 4, 1, 8, 2, 5 👉 모든 노드를 방문함
  • 0 : 방문 완료
    • 1 : 4 가 아직 방문되지 않았으므로 1 을 reserve[4] 에 보관 후 return
    • 3 : 방문 완료
      • 6 : 방문 완료
    • 7 : 방문 완료 (6 이 먼저 방문 되었으므로 문제 없음)
      • 4 : 방문 완료 (4 가 드디어 방문 되었으므로 1 을 이제 방문할 수 있다.reserve[4]인 1 를 바로 다음에 방문하도록 함)
        • 1 : 방문 완료
          • 8 : 방문 완료
          • 2 : 방문 완료
      • 5 : 방문 완료 (8 이 먼저 방문 되었으므로 문제 없음)

order [[4, 1], [8, 7], [6, 5]] 인 경우의 DFS 순회 순서

• 최종 방문순서 👉 0, 3, 6 👉 모든 노드를 방문하지 못 함
  • 0 : 방문 완료
    • 1 : 4 가 아직 방문되지 않았으므로 reserve[4] 에 보관 후 return
    • 3 : 방문 완료
      • 6 : 방문 완료
    • 7 : 8 이 아직 방문되지 않았으므로 7 을 reserve[8] 에 보관 후 return

#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 풀이 ⭕

order [[8, 5], [6, 7], [4, 1]] 인 경우의 BFS 순회 순서

“예약”은 다음에 방문하기 위한 “큐 삽입” 행위를 뜻한다. 큐에 들어간 것은 checked[i] 에 true 로 표시된다.

• 최종 방문순서 👉 0, 3, 6, 7, 4, 1, 8, 5, 2 👉 모든 노드를 방문함
  • 0 : 방문
    • 1 : 4 가 아직 예약되지 않았으므로 1 을 reserve[4] 에 보관 후 예약 안하고 넘어간다.
    • 3 : 예약
    • 7 : 6 이 아직 예약되지 않았으므로 7 을 reserve[6] 에 보관 후 예약 안하고 넘어간다.
  • 3 : 방문
    • 6 : 예약 (6 이 드디어 예약 되었으므로 7 을 이제 예약할 수 있다.reserve[6]인 7 도 예약 함) 7 : 예약
  • 6 : 방문
  • 7 : 방문
    • 4 : 예약 (4 가 드디어 예약 되었으므로 1 을 이제 예약할 수 있다.reserve[4]인 1 도 예약 함)
      • 1 : 예약
    • 5 : 8 이 아직 예약되지 않았으므로 5 을 reserve[8] 에 보관 후 예약 안하고 넘어간다.
  • 4 : 방문
  • 1 : 방문
    • 8 : 예약 (8 이 드디어 예약 되었으므로 5 을 이제 예약할 수 있다.reserve[8]인 5 도 예약 함)
      • 5 : 예약
    • 2 예약
  • 8 : 방문
  • 5 : 방문
  • 2 : 방문

order [[4, 1], [8, 7], [6, 5]] 인 경우의 DFS 순회 순서

• 최종 방문순서 👉 0, 3, 6 👉 모든 노드를 방문하지 못 함
  • 0 : 방문
    • 1 : 4 가 아직 예약되지 않았으므로 1 을 reserve[4] 에 보관 후 예약 안하고 넘어간다.
    • 3 : 예약
    • 7 : 8 이 아직 예약되지 않았으므로 7 을 reserve[8] 에 보관 후 return
  • 3 : 방문
    • 6 : 예약
  • 6 : 방문

#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;
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기