[프로그래머스] 미로 탈출 (2021 카카오 채용연계형 인턴십)

문제 링크

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

코딩테스트 연습 - 미로 탈출

 

풀이

그래프 재정의

트랩에 대해 잘 생각해봅시다.

트랩에 도착하면 트랩과 연결된 모든 간선의 방향이 반대가 됩니다. 그럼 같은 트랩을 두 번 밟으면? 다시 원래대로 돌아옵니다.

트랩끼리 연결되어 있어도 마찬가지입니다. 모든 트랩을 두 번씩 밟으면 원래의 그래프로 돌아옵니다. 결국 특정 트랩을 밟았는지 여부는 최대 한 번까지만 체크하면 되고, 한 번 더 밟게 되면 밟지 않았을 때와 같은 상태라고 생각할 수 있습니다.

 

그럼 각 트랩마다 밟거나, 안 밟거나의 두 가지 상태가 있고, 트랩이 최대 10개 있으므로 많아봐야 $2^{10}$가지 경우의 수가 생깁니다.

 

한 그래프가 매번 바뀐다고 생각하는 것보다 아예 새로운 그래프가 만들어진다고 생각하는 게 정당성을 따지기 더 쉽습니다.

그러니까 그래프를 다시 정의해봅시다.

 

어떤 트랩을 밟았느냐에 따라 각 트랩에 연결된 간선이 뒤집힌 그래프를 얻을 수 있고, 이런 그래프들이 최대 1024개 존재하며, 각 그래프들이 복잡하게 이어진 하나의 그래프를 이루게 됩니다.

 

이해를 위해 간단한 예시를 들어보겠습니다.

원본 그래프는 다음과 같습니다.

 

이 그래프에 트랩 시스템을 적용하면 다음 그림처럼 나타낼 수 있습니다.

그림이 복잡해질 것 같아 정말 간단한 예시를 들어봤습니다. 사실 저 간선들이 어떻게 연결되는지 정확히 알 필요가 없습니다.

결국 중요한 포인트는 여러 개의 그래프들이 긴밀하게 연결되어 있고, 이는 결국 하나의 그래프이므로 최단 거리 알고리즘으로 정답을 구할 수 있다는 것입니다.

 

구현

실제로 그래프를 복잡하게 구현할 필요는 없습니다.

원본 그래프를 유지하되, 각 트랩의 방문 횟수를 참고해 진행 가능한 정점을 제한하는 방식으로 구현합시다.

 

1) 원본 그래프를 기준으로 정방향, 역방향 간선을 각각 저장해둔다.

2) 트랩 방문 횟수를 저장할 배열을 둔다. 어떤 정점이 트랩이 아니라면 이 값은 항상 0이다. 또한, 트랩을 두 번 밟은 경우에도 값이 0이 된다.

3) 다익스트라를 돌린다.

  3-1) 한 정점에 연결된 모든 간선(정방향, 역방향)을 확인한다.

  3-2) 이때, 현재 정점을 $u$라 하고, 간선에 연결된 정점을 $v$라 했을 때, 과정 2의 배열 값을 참고하여 $u$, $v$의 방문 횟수 합으로 해당 간선이 유효한지 판단한다.

  3-3) 간선이 정방향이고 방문 횟수 합이 짝수이거나, 간선이 역방향이고 방문 횟수 합이 홀수라면 유효하다.

4) 답을 출력하도록 하자.

 

• 2에서 배열이라고 적어놨지만 사실 저는 map을 이용했습니다.
• 3-3이 홀, 짝으로 어떻게 유효 판단이 되는 건지 더 설명을 하기엔 너무 길어질 것 같아 따로 적지 않았습니다. 혹시 궁금하시면 댓글로 달아주세요.
• 구현 방식은 사람마다 많이 갈릴 듯합니다.

 

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vvi = vector<vi>;
const int INF = 0x3f3f3f3f;
 
struct Edge {
    int to, cost;
 
    Edge(int t = 0, int c = 0) : to(t), cost(c) {}
};
 
struct Node {
    vector<Edge> ori, rev;
};
vector<Node> p;
vb isTrap;
 
int go(int st, int ed) {
    // {{ n, (맵 상태) }, bool }
    map<pair<int, map<int, int>>, bool> chk;
    priority_queue<tuple<int, int, map<int, int>>> q;
    q.push({0, st, map<int, int>()});
    while (!q.empty()) {
        auto[dist, now, state] = q.top();
        q.pop();
        if (now == ed) return -dist;
        if (auto &c = chk[{now, state}]; c) continue;
        else c = true;
 
        auto push = [&](int dist, int now, auto state, int next, int cost) {
            if (isTrap[next]) state[next] = (state[next] + 1) % 2;
            if (!chk[{next, state}]) {
                q.push({dist - cost, next, state});
            }
        };
 
        for (Edge &e: p[now].ori) {
            auto[next, cost] = e;
            if ((state[now] + state[next]) % 2 == 0) {
                push(dist, now, state, next, cost);
            }
        }
        for (Edge &e: p[now].rev) {
            auto[next, cost] = e;
            if (state[now] + state[next] == 1) {
                push(dist, now, state, next, cost);
            }
        }
    }
 
    return INF;
}
 
int solution(int n, int start, int end, vvi roads, vi traps) {
    p.resize(n + 1);
    isTrap.resize(n + 1);
    for (vi &road: roads) {
        int u = road[0], v = road[1], c = road[2];
        p[u].ori.emplace_back(v, c);
        p[v].rev.emplace_back(u, c);
    }
    for (int &trap: traps) {
        isTrap[trap] = true;
    }
 
    return go(start, end);
}