[BOJ] 탈옥

문제

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.

평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.

상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

풀이

9376

맞았습니다!!

2172

8

C++14 / 수정

3395

22초 전

 

1. 0-1 BFS (가중치가 있는 탐색)

 

2. 문이 존재 = 가중치 1

문이 존재X = 가중치 0

 

3. 총 세가지 탈출 경우가 있다. 

• 죄수 1이 죄수 2를 데리고 탈출 
• 죄수 2가 죄수 1을 데리고 탈출
• 상근이가 죄수 모두를 데리고 탈출 

4. 총 세 가지 경우를 모두 탐색하고 값을 가중치를 저장하는 이차원 배열 dist에 저장한다. 

 

5. dist에 저장된 값이 최소값인 경우가 문을 최소로 여는 가중치이다. 

 

6. 최소값 비교할 때 주의할 점은 문을 세명이서 다같이 여는 경우는 없기 때문에 -2를 해준다. (한명이 열었다고 가정함)

 

7. 여기서 아이디어(?)가 필요했던 곳은 평소에 최단 거리하면 우선순위큐를 사용하는 경우가 많았는데 이 문제에서는 dequeue를 사용해야 한다. 덱? 디큐? 

 

8. deque 는 만약 문이 있는 곳을 지나면 가장 마지막에 삽입하여 그 지점을 가장 나중에 지나도록 하고 

문이 없는 곳을 지나면 가장 처음에 삽입하여 먼저 지나가도록 하여 최단 거리를 만든다. 

 

9. 비슷한 문제 (=다익스트라 알고리즘)

2019/10/24 - [BOJ/C++] - [BOJ] 알고스팟

불러오는 중입니다...

---

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
 
using namespace std;
 
char map[102][102];
int dist[102][102];
typedef pair<int, int> pp;
 
pp prisons[3];
 
int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};
 
void bfs(int h, int w) {
    for (int i = 0; i < 3; i++) {
        //세명이 탐색한 가중치를 모두 더하는 작업 
        int c_dist[102][102]; //가중치를 dist에 최종으로 더해주기 위해 임시로 만든다. 
        memset(c_dist, -1, sizeof(c_dist));
 
        deque<pp> dq;
        dq.push_front(prisons[i]);
 
        c_dist[prisons[i].first][prisons[i].second] = 0;
 
        while(!dq.empty()) {
            int x = dq.front().first;
            int y = dq.front().second;
 
            dq.pop_front();
 
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
 
                if (nx < 0 || nx >= h+2 || ny < 0 || ny >= w+2 || map[nx][ny] == '*' || c_dist[nx][ny] > -1) continue;
                //이미 한 번 방문한 곳이거나, 벽인 경우
 
                if (map[nx][ny] == '#') {
                    //가중치 +1
                    c_dist[nx][ny] = c_dist[x][y] + 1;
                    dq.push_back(pp(nx, ny)); //가장 마지막에 넣어서 최대한 가중치가 적은 길로 먼저 가도록 경로를 조성
                } 
                else {
                    c_dist[nx][ny] = c_dist[x][y];
                    dq.push_front(pp(nx, ny)); //가장 첫번째로 넣어서 바로 다음에 이 좌표로 갈 수 있도록 한다. 
 
                }
            }
           
        }
         //가중치를 전부 구했다면 이제 최종 가중치에 더해준다. 
         for (int j = 0; j < h+2; j++) {
             for (int k = 0; k < w+2; k++ ) {
                 dist[j][k] += c_dist[j][k];
             }
         }
    }   
 
 
}
void init() {
    memset(map, '0', sizeof(map));
    memset(dist, 0,sizeof(dist));
 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int tc;
 
    cin >> tc;
 
    for (int t= 0; t < tc; t++) {
        int w, h;
 
        cin >> h >> w;
 
        init();
        
        bool flag = false;
        int idx = 1;
        prisons[0].first = 0;
        prisons[0].second = 0; //상근이(=조력자)의 위치 
 
        for (int i = 1; i < h+1; i++) {
            for (int j = 1; j < w+1; j++) {
                cin >> map[i][j];
 
                if (map[i][j] == '$') {
                    if (!flag) {
                        prisons[idx].first = i;
                        prisons[idx++].second = j;
                        flag= true;
                    }
                    else {
                        prisons[idx].first = i;
                        prisons[idx].second = j;
                    }
                }
            }
        }//input 
 
        bfs(h, w);
 
        int ans = 987654321; 
 
        //가중치 최소값 비교 
        for (int i = 0; i< h+1; i++) {
            for (int j = 0; j < w+1; j++) {
                if (map[i][j] == '*') continue; //벽 
                if (map[i][j] == '#') {
                    //세명 다 문을 열었을 가능성을 빼준다. 
                    dist[i][j] -= 2;
 
                }
 
                if (dist[i][j] < ans) ans = dist[i][j];
            }
        }
        cout << ans << '\n';
    }
 
 
    return 0;
}