[백준/C++] 5427번. 불

[백준/C++] 5427번. 불

1. 문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

3. 출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

4. 풀이

• BFS로 풀었다.
• 각 테스트 케이스마다 BFS를 하였다.
• 우선, 지도를 탐색하며 불의 위치와 상근이의 시작 위치를 모두 큐에 삽입한다.
  • 이때, 상근이의 위치는 불의 위치를 모두 삽입한 후에 삽입한다.
  • 상근이는 불이 번질 위치에도 가면 안되기 때문에 불이 번지는 작업을 먼저하고 상근이의 이동작업을 처리하기 위함이다.
  • 큐에 삽입하였을때 불인지 상근인지 구분하는 type을 추가해서 큐에 삽입한다.
• 큐에서 하나씩 꺼내서 작업을 진행한다.
• 불과 상근이 모두 이미 불이 있는 곳과 벽으로는 이동할 수 없기 때문에 벽이 거나 이미 불이 번진 곳은 continue로 무시한다.
• 이동할 곳이 벽이 아니고 불이 번진 곳도 아닌 경우,
  • 이동할 주체가 불인 경우 map에서 이동할 위치를 불로 바꾸고 큐에 삽입한다.
  • 이동할 주체가 상근이인 경우 이미 방문한 적이 있으면 무시하고 그렇지 않으면 route 배열의 값을 변경하고 큐에 삽입한다.
• 큐에서 꺼낸 값이 배열의 테투리인 경우 현재 route + 1 한 값을 리턴한다.
• while-loop가 끝날 때까지 탈출하지 못하면 INF 값을 리턴한다.

5. 처음 코드와 달라진 점

• 상근이의 위치를 찾고 나서 해당 위치를 .으로 표시하도록 변경하였다.
• 이동할 위치를 구하는 수식을 잘못 써서 변경하였다.

6. 코드

#include <iostream>
#include <algorithm>
#include <queue>
#define INF 987654321
using namespace std;

int n, m;
char map[1000][1000];
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

int bfs() {
  int route[1000][1000] = {0, };
  queue<pair<int, pair<int, int> > > q;

  int startX, startY;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (map[i][j] == '@') {
        startX = i;
        startY = j;
        map[i][j] = '.';
      }
      else if (map[i][j] == '*') {
        q.push(make_pair(1, make_pair(i, j)));
      }
    }
  }
  q.push(make_pair(0, make_pair(startX, startY)));
  
  while (!q.empty()) {
    int type = q.front().first;
    int x = q.front().second.first;
    int y = q.front().second.second;
    q.pop();

    if (type == 0 && (x == 0 || x == n - 1 || y == 0 || y == m - 1)) return route[x][y] + 1;

    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (map[nx][ny] == '#' || map[nx][ny] == '*') continue;
      
      if (type == 0) {
        if (route[nx][ny] != 0 || (nx == startX && ny == startY)) continue;
        route[nx][ny] = route[x][y] + 1;
        q.push(make_pair(type, make_pair(nx, ny)));
      }
      else {
        map[nx][ny] = '*';
        q.push(make_pair(type, make_pair(nx, ny)));
      }
    }
  }
  
  return INF;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int testCase;
  cin >> testCase;
  for (int tc = 0; tc < testCase; tc++) {
    cin >> m >> n;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cin >> map[i][j];
      }
    }

    int answer = bfs();
    if (answer == INF) cout << "IMPOSSIBLE\n";
    else cout << answer << endl;
  } 
}