[백준 9376번] 탈옥

문제 링크

https://www.acmicpc.net/problem/9376

 

문제 요약

두 죄수 A, B가 최소한의 문을 열어 감옥에서 탈출하려고 한다. 한 죄수가 문을 열면, 그 문은 계속 열려 있어서 다른 죄수도 그 문을 이용할 수 있다.

(원래 문제에서는 감옥 밖에 있는 상근이가 특별한 기술을 이용해 문을 열어준다고 되어 있지만, 문제를 더 쉽게 이해할 수 있게 내용을 살짝 바꿨다.)

 

문제 풀이

가장 먼저 떠오르는 생각은 두 죄수의 상태를 동시에 관리하는 것이다. 하지만 죄수가 있을 수 있는 장소는 1만 곳이고, 이를 두 죄수의 상태로 표현하면 1억 가지의 경우의 수가 생긴다. 여기에 탈출을 위해 이용한 문의 개수까지 고려한다면 이 방법은 문제를 제한 시간 내에 풀 수 있는 방법이 아니다.

 

경우의 수 나누기

이 문제를 풀기 위해서는 두 죄수가 어떤 전략을 가지고 움직여야 최적해를 찾을 수 있을지 경우의 수를 나눠야 한다. 죄수 A와 B는 최적해를 위해 아래 두 가지 전략 중에 하나를 선택할 수 있다.

1. 죄수 A와 B가 따로 탈출한다.
2. 죄수 A와 B는 어느 한 점에 만나 함께 탈출한다.

1번 전략을 선택했을 경우, 최적해가 될 수 있다는 것은 직관적으로 이해할 수 있다. 하지만 2번 전략의 경우, 반드시 한 지점에서 만나서 같이 움직여야 최적해가 된다는 점이 와닿지 않을 수 있다. 그러면 A와 B가 만난 뒤 따로 움직이는 경우가 최적해라고 가정을 해보자. A와 B가 만난 다음, A가 사용한 문들을 B가 사용하지 않고 따로 움직였을 때 최적해가 된다면, 그냥 A가 B를 따라가면 더 좋은 최적해가 되지 않을까? 즉 이 가설 자체가 모순이기 때문에 A와 B가 만나면 항상 같이 다니는 것이 최적해라는 것을 알 수 있다.

 

최적해는 두 가지 경우 중 하나에서 나온다는 것을 알았으니, 이제 각각의 경우에서 최적해를 구한 다음에 그중 더 작은 값을 출력하면 문제를 풀 수 있다.

 

그래프 모델링 하기

최적해를 구하기 전에 문제에서 주어진 감옥을 그래프로 모델링 해보자. 2차원 행렬을 그래프로 모델링할 때 1차원으로 압축시키면 문제를 더 쉽게 풀 수 있다.

int getIdx(int i, int j) {
    return i * w + j;
}

그다음 각 노드들 간의 관계를 가중치가 있는 그래프로 표현할 수 있다. 빈칸에서 문으로 이동할 때는 가중치를 1로 두고, 빈칸에서 빈칸, 문에서 빈칸으로 이동할 때는 가중치를 0으로 모델링하면 탈출할 때 최소한의 문을 사용하는 조건을 최단거리를 구하는 문제로 바꿔 풀 수 있게 된다.

 

그런데 A와 B가 탈출했다는 것을 어떻게 탐지할 수 있을까? 벽이 아닌 모서리에 도착했을 때 A와 B가 탈출했다고 판단을 할 수 있다. 그러나 탈출 지점을 의미하는 가상의 노드를 하나 만들어 벽이 아닌 모서리들과 연결하면, 하나의 노드만 보고도 A와 B가 탈출했다는 것을 알 수 있게 된다.

 

다익스트라를 이용해 답을 구하기

다익스트라 알고리즘을 이용해 최단거리를 구한 다음 각각의 경우에 수에 대해 최적해를 계산해 준다. 먼저 A와 B가 따로 탈출하는 경우를 계산해 보자.

int case1_ans = dijkstra(A_IDX, EXIT_IDX) + dijkstra(B_IDX, EXIT_IDX);

그다음은 A와 B가 한 지점에 만나서 같이 탈출하는 경우의 최적해를 구해야 한다. A와 B가 어느 곳에서 만나야 최적의 경우인지 모르니 만날 수 있는 모든 곳에 대해서 최적해를 계산해 준다. 만약 A와 B가 만나는 곳이 문이라면 한 명만 문을 열면 되니 1을 빼준다.

int case2_ans = INF;

for (int i = 0 ; i < h ; ++i) {
    for (int j = 0 ; j < w ; ++j) {
        if (A[i][j] == '*') {
            continue;
        }
        
        int MEETING_IDX = getIdx(i, j);
        
        int dist = dijkstra(A_IDX, MEETING_IDX) + dijkstra(B_IDX, MEETING_IDX) + dijkstra(MEETING_IDX, EXIT_IDX);
        
        if (A[i][j] == '#') {
            dist -= 1;
        }
        
        case2_ans = min(case2_ans, dist);
    }
}

 

여기서 끝나면 좋겠지만, 이대로 제출하면 시간초과가 발생한다. 만날 수 있는 지점이 1만 개나 되기 때문에 다익스트라를 1만 번이나 돌려야 하며, 거기다 테스트 케이스까지 있으니 시간초과가 나는 것은 당연한 일이다.

 

다익스트라 결과 배열을 이용해 답을 구하기

A와 B가 만날 수 있는 지점마다 다익스트라를 매번 새롭게 돌려야 해서 시간초과가 발생한다. A와 B가 만날 수 있는 모든 지점들에 대해서 탈출 지점까지 가는 최단 거리를 빠르게 구할 수 있는 방법이 없을까? 우리가 모델링한 그래프가 무향 그래프이기 때문에 출발 지점과 도착 지점을 반대로 생각해도 최단거리가 똑같다는 점을 이용할 수 있다. 탈출 지점에서 다익스트라를 한 번 돌리면 탈출 지점에서 시작해 도달할 수 있는 모든 지점들에 대한 최단거리를 구할 수 있고, 결국 이 값들이 각 지점에서 탈출 지점으로 가는 최단 거리가 된다.

vector<int> startFromA = dijkstra2(A_IDX);
vector<int> startFromB = dijkstra2(B_IDX);
vector<int> startFromExit = dijkstra2(EXIT_IDX);

int ans = startFromA[n - 1] + startFromB[n - 1];

for (int i = 0 ; i < h ; ++i) {
    for (int j = 0 ; j < w ; ++j) {
        if (A[i][j] == '*') {
            continue;
        }
        
        int MEETING_IDX = getIdx(i, j);
        
        int dist = startFromA[MEETING_IDX] + startFromB[MEETING_IDX] + startFromExit[MEETING_IDX];
        
        if (A[i][j] == '#') {
            dist -= 2;
        }
        
        ans = min(ans, dist);
    }
}

printf("%d\n", ans);

한 가지 주의할 점은 A와 B가 한 지점에서 만나서 같이 움직일 때의 최적해를 구할 때, 만나는 곳이 문이라면 1이 아니라 2를 빼줘야 한다는 것이다. 왜냐면 이 전과 다르게 탈출 지점에서 만나는 곳까지 오는 것으로 계산했기 때문이다.

 

어렵다고 생각할 수 있는 지점을 최대한 쉽게 설명하려고 하다보니 생각했던 것보다 글이 너무 길어졌다. 설명이 길어진 만큼 누군가에게는 쉽게 전달이 됐으면 좋겠다.

 

소스 코드

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

const int INF = 10000000;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int t, h, w, n;
char A[110][110];
vector<vector<pair<int, int>>> nodes;

int getIdx(int i, int j) {
    return i * w + j;
}

void buildGraph() {
    nodes.assign(n, vector<pair<int, int>>());
    
    for (int i = 0 ; i < h ; ++i) {
        for (int j = 0 ; j < w ; ++j) {
            if (A[i][j] == '*') {
                continue;
            }
            
            int here = getIdx(i, j);
            
            for (int k = 0 ; k < 4 ; ++k) {
                int ni = i + dx[k], nj = j + dy[k];
                
                if (ni == -1 || ni == h || nj == -1 || nj == w) {
                    nodes[here].push_back({ n - 1, 0 });
                    nodes[n - 1].push_back({ here, A[i][j] == '#' ? 1 : 0 });
                } else if (A[ni][nj] != '*') {
                    int there = getIdx(ni, nj);
                    nodes[here].push_back({ there, A[ni][nj] == '#' ? 1 : 0 });
                }
            }
        }
    }
}

vector<int> dijkstra2(int src) {
    vector<int> dist(n, INF);
    priority_queue<pair<int, int>> pq;
    
    dist[src] = 0;
    pq.push({ 0, src });
    
    while (!pq.empty()) {
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        
        if (dist[here] < cost) {
            continue;
        }
        
        for (const auto& node: nodes[here]) {
            int there = node.first;
            int nextDist = cost + node.second;
            
            if (dist[there] > nextDist) {
                dist[there] = nextDist;
                pq.push({ -nextDist, there });
            }
        }
    }
    
    return dist;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &t);
    
    while (t--) {
        scanf("%d%d", &h, &w);
        
        n = h * w + 1;

        int A_IDX = -1, B_IDX = -1, EXIT_IDX = n - 1;
        
        for (int i = 0 ; i < h ; ++i) {
            scanf("%s", A[i]);
            
            for (int j = 0 ; j < w ; ++j) {
                if (A[i][j] == '$') {
                    if (A_IDX == -1) {
                        A_IDX = getIdx(i, j);
                    } else {
                        B_IDX = getIdx(i, j);
                    }
                }
            }
        }
        
        buildGraph();
        
        vector<int> startFromA = dijkstra2(A_IDX);
        vector<int> startFromB = dijkstra2(B_IDX);
        vector<int> startFromExit = dijkstra2(EXIT_IDX);
        
        int ans = startFromA[n - 1] + startFromB[n - 1];
        
        for (int i = 0 ; i < h ; ++i) {
            for (int j = 0 ; j < w ; ++j) {
                if (A[i][j] == '*') {
                    continue;
                }
                
                int MEETING_IDX = getIdx(i, j);
                
                int dist = startFromA[MEETING_IDX] + startFromB[MEETING_IDX] + startFromExit[MEETING_IDX];
                
                if (A[i][j] == '#') {
                    dist -= 2;
                }
                
                ans = min(ans, dist);
            }
        }

        printf("%d\n", ans);
    }
}