[백준 / BOJ] C++ 4179 불!

4179번: 불!

 

문제

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

4179번: 불!

 

 

풀이

재민이가 불을 피해 가장자리로 가서 탈출할 수 있으면 탈출하는 최단 시간을, 탈출할 수 없으면 IMPOSSIBLE을 출력하는 문제다.

 

틀린 풀이

BFS를 시작할 때 재민이는 1부터 시작하고 불은 1001부터 시작하도록 해서 재민이 먼저 이동, 그다음 불이 이동하도록 했다. 이동할 때마다 visited 배열 값이 1씩 증가하도록 해서 시간을 계산했다. 큐에서 나온 값이 불이면(1000 이상) 다음 칸이 불이 아니면 진행하고 재민이면 방문하지 않은 칸으로만 진행했다. 가장자리에 재민이가 도달하면 visited 값을 return 해주도록 했다.

 

그러나 만약 불이 재민이가 큐에 들어있는데 해당 위치의 재민이가 불에게 잡힌 경우, 재민이보다 불이 먼저 BFS를 하게 되어 반례가 생긴다. 그래서 바꾼 풀이가 아래 풀이다.

 

맞은 풀이

접근법은 재민이와 불에 대해 각각 BFS를 사용하는 것이다. 각각에 대해 1부터 시작해 이동할 때마다 +1 해가며 BFS를 한다. 이제 가장자리를 모두 탐색하며 재민이가 도달한 위치일 때, 불보다 빨리 도착한 경우와 불이 아예 안 온 경우 재민이가 걸린 시간을 배열에 추가해 줬다. 그러면 배열에 담긴 값들은 답이 될 수 있는 후보들이고 문제에서 요구하는 것은 가장 빠른 탈출 시간이므로 최솟값을 출력하면 된다. 만약 배열이 비어있다면 IMPOSSIBLE을 출력하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

string graph[1001];
int R, C;
int visitedJ[1001][1001];
int visitedF[1001][1001];
int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};
queue<pair<int, int>> qJ, qF;
vector<int> ans;

void bfsJ() {
  while (!qJ.empty()) {
    int x = qJ.front().first;
    int y = qJ.front().second;
    qJ.pop();
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      // 범위를 벗어나면
      if (nx < 0 || nx >= R || ny < 0 || ny >= C)
        continue;
      // 방문하지 않았고, 지나갈 수 있다면
      if (!visitedJ[nx][ny] && graph[nx][ny] != '#') {
        visitedJ[nx][ny] = visitedJ[x][y] + 1;
        qJ.push({nx, ny});
      }
    }
  }
}

void bfsF() {
  while (!qF.empty()) {
    int x = qF.front().first;
    int y = qF.front().second;
    qF.pop();
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      // 범위를 벗어나면
      if (nx < 0 || nx >= R || ny < 0 || ny >= C)
        continue;
      // 방문하지 않았고, 지나갈 수 있다면
      if (!visitedF[nx][ny] && graph[nx][ny] != '#') {
        visitedF[nx][ny] = visitedF[x][y] + 1;
        qF.push({nx, ny});
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> R >> C;
  for (int i = 0; i < R; i++) {
    cin >> graph[i];
    for (int j = 0; j < C; j++) {
      // 방문 초기화
      visitedJ[i][j] = 0;
      visitedF[i][j] = 0;
      // 재민이의 위치 추가, 시작 지점 방문 1로
      if (graph[i][j] == 'J') {
        qJ.push({i, j});
        visitedJ[i][j] = 1;
      }
      // 불의 위치 추가, 시작 지점 방문 1로
      if (graph[i][j] == 'F') {
        qF.push({i, j});
        visitedF[i][j] = 1;
      }
    }
  }
  // 재민이와 불에 대해 각각 BFS
  bfsJ();
  bfsF();
  // 가장자리를 탐색하여 답일 수 있는 경우 ans에 추가
  for (int i = 0; i < R; i++) {
    if (visitedJ[i][0] && (visitedJ[i][0] < visitedF[i][0] || !visitedF[i][0]))
      ans.push_back(visitedJ[i][0]);
    if (visitedJ[i][C - 1] && (visitedJ[i][C - 1] < visitedF[i][C - 1] || !visitedF[i][C - 1]))
      ans.push_back(visitedJ[i][C - 1]);
  }
  for (int i = 0; i < C; i++) {
    if (visitedJ[0][i] && (visitedJ[0][i] < visitedF[0][i] || !visitedF[0][i]))
      ans.push_back(visitedJ[0][i]);
    if (visitedJ[R - 1][i] && (visitedJ[R - 1][i] < visitedF[R - 1][i] || !visitedF[R - 1][i]))
      ans.push_back(visitedJ[R - 1][i]);
  }
  // ans가 비어있으면 IMPOSSIBLE, 이외엔 최솟값 출력
  if (ans.empty())
    cout << "IMPOSSIBLE\n";
  else
    cout << *min_element(ans.begin(), ans.end()) << '\n';
  return 0;
}