[백준] 9376번 탈옥

9376 탈옥

문제

---

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

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

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

입력

---

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

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

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

출력

---

각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최솟값을 출력한다.

---

풀이)

문을 0개, 1개, 2개, ... , 최종 문개수까지 조합해서 없애는 방법은 시간이 오래 걸린다.

문을 없앤다에 주목하지 말고, 사람에 주목해서 풀어야 하는 문제이다.

죄수 2명이 탈출할 수 있는 방법은 3가지가 있다.

1. 상근이가 죄수 1, 2를 찾아 탈출하는 경우

2. 죄수 1가 죄수 2도 찾아 탈출하는 경우

3. 죄수 2가 죄수 1도 찾아 탈출하는 경우

3명이 각자 문을 열면서 탐색하면 어느 시점에 만날 것이다.

그 시점에 모두 탈출이 가능하다고 본다.

따라서

3가지 경우 각자

bfs를 통해 이동하면서 그 위치까지 가는데 문 여는 횟수 값들을 배열로 저장한다. 

ex) person1[i][j] = (i,j)위치까지 person1이 문을 몇개 열고 왔는지 횟수 저장 

   (빈 공간을 지나가면 횟수 증가 x, 문을 지나가면 횟수 +1)

그리고 3개의 배열 값들을 모두 더한 뒤, 

문은 한 번만 열면 되니깐 문 위치 지점의 배열 값은 -2를 해주고 ( 3명이 동시에 열 필요는 없음)

값 중 최소값을 찾는다. 그 최소값이 문을 여는 최소 횟수이다.

참고사항

- 문 여는 횟수가 중요하므로 상근이가 감옥 바깥의 어느 위치에서 시작하는 지는 상관없다.

 그러므로 상근이는 쉽게 (0,0)에서 시작하기로 한다.

- 문의 개수가 최소인 것이 중요하므로 BFS에서 queue 사용하는 것이 아닌, prioirty_queue를 사용하겠다.

  -> 문의 횟수가 적을 수록 탐색 우선순위가 높게끔. (시간을 절약가능)

   

  (priority_queue는 기본이 내림차순이므로 greater<int>를 사용해서 오름차순으로 바꿔주겠다) 

- 문 여는 횟수를 저장하는 배열의 초기값을 가장 큰 값으로 초기화 해둔다.

  (그래야 문 여는 횟수가 적은 값이면 update하며 이동하게끔 할 수 있다.)

코드)

#include <stdio.h>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <functional>
using namespace std;
#define INF 999999999
int h, w;
char map[102][102];
bool visited[102][102];
int door[102][102][3];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector <pair<int, int>> person;
 
int main() {
    int test_case;
    scanf("%d", &test_case);
 
    
    while (test_case--) {
        scanf("%d %d", &h, &w);
        getchar();
        //감옥 주위는 .으로 둘러싸기
        //위 아래
        for (int i = 0; i <= w + 1; i++) {
            map[0][i] = '.';
            map[h + 1][i] = '.';
        }
        //양 옆
        for (int i = 1; i <= h; i++) {
            map[i][0] = '.';
            map[i][w + 1] = '.';
        }
        person.push_back({ 0,0 });//상근이
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                scanf("%c", &map[i][j]);
                if (map[i][j] == '$') {
                    person.push_back({ i,j });//죄수
                }
            }
            getchar();
        }
 
        for (int i = 0; i <= h + 1; i++) {
            for (int j = 0; j <= w + 1; j++) {
                for (int k = 0; k < 3; k++) {
                    door[i][j][k] = INF;
                }
            }
        }
 
        //상근이, 죄수1, 죄수2순으로
        for (int i = 0; i < 3; i++) {
 
            for (int i = 0; i <= h + 1; i++) {
                for (int j = 0; j <= w + 1; j++) {
                    visited[i][j] = false;
                }
            }
            priority_queue < pair<int, pair<int, int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> qu;
            qu.push({ 0,{person[i]} }); //처음 출발위치
            door[person[i].first][person[i].second][i] = 0;
 
            while (!qu.empty())
            {
                int cost = qu.top().first;
                int y = qu.top().second.first;
                int x = qu.top().second.second;
                qu.pop();
                for (int t = 0; t < 4; t++) {
                    int ny = y + dy[t];
                    int nx = x + dx[t];
                    int next_cost = cost;
 
                    if (ny<0 || ny>h + 1 || nx<0 || nx>w + 1) continue;
                    if (visited[ny][nx] || map[ny][nx] == '*')continue;
 
                    if (map[ny][nx] == '#') next_cost++;//문이라면 횟수 증가
 
                    if (door[ny][nx][i] > next_cost) {
                        door[ny][nx][i] = next_cost;
                        visited[ny][nx] = true;
                        qu.push({ next_cost,{ny,nx} });
                    }
                }
            }
 
            
        }
        
 
        long long result = LLONG_MAX;
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                if (map[i][j] == '*')continue;
                long long temp = 0;
                for (int k = 0; k < 3; k++) {
                    temp += door[i][j][k];
                }
                if (map[i][j] == '#') temp -= 2;
 
                result = min(result, temp);
            }
        }
        printf("%lld\n", result);
 
        //다음 testcase를 위해 초기화
        person.clear();
    }
    return 0;
}