백준 9376 / 탈옥

이 문제를 단번에 풀었다면 나는 당장 하산했을 것이다.

처음 문제를 풀었을 때 여러가지 해결법이 떠올랐다.

그중 가장 그럴 듯 했던건 모든 문의 좌표를 받고 

0개를 열었을 때, 1개를 열었을 때, 2개를 열었을 때 ...... n개를 열었을 때

탈옥에 성공하는 문의 최소개수를 구하는 방법이었는데. 

한 케이스당 bfs를 2번씩 해야되니 시간초과에 걸렸다. 맵이 작았으면 괜찮았을 텐데..

이 문제의 해결법은 이렇다.

죄수1과 죄수2 그리고 맵 밖에 있는 사람이 있다고 가정하자. (문제에 힌트가 있다. 상근이는 어디에나 있을 수 있다고..)

맵도 바꿔준다.

맵의 가장자리 부분에 빈공간(.)를 추가시켜준다.

그리고 죄수1과 죄수2 밖의사람의 모든 dist를 bfs로 구한다

이떄 문이 아닌 빈 공간을 지나가는 경우는 가중치가 0이고 문을 지나가는 것은 가중치가 1이다. 

이 점 때문에 시간을 줄이기 위해 queue 대신 deque를 써야한다.

그냥 빈공간을 지나가는 경우 push_front, 문을 지나가는 경우 push_back.

죄수1과 죄수2 밖의사람의 dist를 모두 구했다면 전부 더해준다.

이떄, 벽이라면 그냥 continue (벽을 지나가는건 말이 안되기 떄문에)

문이라면 더한 값에 -2를 해주어야한다. (문 하나를 세번 연 것으로 치기때문에 한 번만 연 것으로 표시하기 위해)

이렇게 더한 dist에서 최소값을 출력하면 답이다.

이 아이디어는 

죄수1이 죄수2과 (x,y)에서 만나서 밖으로 나가는 로직에서 한 단계 발전시킨 것이다.

죄수1와 죄수2가 만나서 밖에 나가는 로직은 bfs를 총 n x m 만큼 해야되기 떄문에 비효율적.

그리하여 밖에 있는 사람도 감옥안에 들어오면서 죄수1과 죄수2를 만나는 로직을 세운 것이다.

진짜,

이 문제를 단번에 풀었다면 나는 당장 하산했을 것이다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
#include<memory.h>
 
using namespace std;
 
bool check[105][105];
 
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
int h, w;
 
deque<pair<int, int>>dq;
 
vector<vector<int>>go(vector<vector<char>>map, int x, int y) {
 
    vector<vector<int>>dist(h + 2, vector<int>(w + 2, 0));
 
    memset(check, false, sizeof(check));
    dist[x][y] = 0;    
    dq.push_front({ x,y });
 
    while (!dq.empty()) {
        int x = dq.front().first;
        int y = dq.front().second;
        dq.pop_front();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < h + 2 && ny < w + 2) {
                if (check[nx][ny] == false) {
                    if (map[nx][ny] == '.' || map[nx][ny] == '$') {
                        check[nx][ny] = true;
                        dist[nx][ny] = dist[x][y];
                        dq.push_front({ nx,ny });
                    }
                    if (map[nx][ny] == '#') {
                        check[nx][ny] = true;
                        dist[nx][ny] = dist[x][y] + 1;
                        dq.push_back({ nx,ny });
                    }
                }
            }
        }
    }
 
    return dist;
}
int main() {
    
    //freopen("Text.txt", "r", stdin);
 
    int testcase;
    cin >> testcase;
    
    while (testcase--) {
 
 
        vector<vector<char>>map(105, vector<char>(105));
        vector<pair<int, int>>pri;
 
        cin >> h >> w;
        
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> map[i+1][j+1];
            }
        }
 
        bool first = false;
 
        for (int i = 0; i < h + 2; i++) {
            for (int j = 0; j < w + 2; j++) {
                if (map[i][j] == NULL) {
                    map[i][j] = '.';
                }
                if (map[i][j] == '$') {
                    pri.push_back({ i,j });
                }
            }
        }
 
        vector<vector<int>>dist00 = go(map,0, 0);
        vector<vector<int>>dist1 = go(map,pri[0].first, pri[0].second);
        vector<vector<int>>dist2 = go(map, pri[1].first, pri[1].second);
 
        int min = h*w;
 
        for (int i = 0; i < h + 2; i++) {
            for (int j = 0; j < w + 2; j++) {
                if (map[i][j] == '*') {
                    continue;
                }
                int a = dist00[i][j];
                int b = dist1[i][j];
                int c = dist2[i][j];
 
                int cur = a + b + c;
        
                if (map[i][j] == '#') {
                    cur = cur - 2;
                }
                if (min > cur) {
                    min = cur;
                }
            }    
        }
        cout << min << endl;
 
    }
}