[프로그래머스] 67260 동굴 탐험 (C/C++)

문제

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

풀이

전형적인 그래프 탐색 문제였다. 모든 노드를 탐색만 한다면 어떤 알고리즘을 사용해도 상관 없을 것 같다. 처음엔 DFS로 구현했는데, 잠긴 곳을 열고 다시 방문하는 과정에서 0번 노드부터 다시 시작할 경우 시간 복잡도가 커지는 문제가 발생했다. 탐색 알고리즘을 BFS로 수정 후, 잠긴 노드를 열었을 때 해당 노드가 대기열에 있다면 바로 큐에 추가하는 방식으로 해결했다. 이 방식은 잠긴 노드를 연 후에 다시 돌아가거나 0번 노드부터 다시 시작하지 않기 때문에 시간 복잡도가 증가하지 않는 장점이 있다.

보통 이렇게 특정 노드부터 출발한다고 명시하는 문제들은 해당 노드를 무조건 방문할 수 있도록 조건이 제시되어있는데, 이번 문제에서는 0번 노드가 잠겨있을 수도 있었다. 문제에 0번 노드는 무조건 잠겨있지 않다는 조건이 없었는데 이를 간과하고 코드를 작성했다가, 제출 후 여러 번 틀렸다고 나와서 무엇이 문제였을까 꽤 오래 고민했다. 문제를 꼼꼼히 읽고 습관에 사로잡히지 않도록 주의해야겠다.

소스 코드

C++17

#include <bits/stdc++.h>

bool solution(int n, std::vector<std::vector<int>> edges, std::vector<std::vector<int>> orders) {
    std::unordered_set<size_t> locked;
    std::unordered_map<size_t, size_t> keys;

    for (const auto &order: orders) {
        keys[order[0]] = order[1];
        locked.insert(order[1]);
    }

    if (locked.count(0)) {
        return false;
    }

    std::vector<std::vector<size_t>> graph(n);

    for (const auto &edge: edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    std::vector<size_t> visited(n, false);
    std::queue<size_t> queue;
    std::unordered_set<size_t> pending;

    visited[0] = true;
    queue.push(0);
    while (!queue.empty()) {
        const size_t current = queue.front(); queue.pop();

        if (keys.count(current)) {
            if (pending.count(keys[current])) {
                queue.push(keys[current]);
                pending.erase(keys[current]);
            }
            locked.erase(keys[current]);
            keys.erase(current);
        }

        for (const size_t next: graph[current]) {
            if (visited[next]) {
                continue;
            }
            visited[next] = true;
            if (locked.count(next)) {
                pending.insert(next);
            } else {
                queue.push(next);
            }
        }
    }

    return locked.empty();
}

[프로그래머스] 67260 동굴 탐험 (C/C++)

문제

풀이

소스 코드

Share this post