[백준 / BOJ] C++ 5427 불

5427번: 불

 

문제

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

5427번: 불

 

 

풀이

입력 형식과 주어진 횟수의 테스트 케이스를 반복하는 점을 제외하고 4179번 불! 문제와 완전히 똑같은 문제다. 4179번 불! 문제의 풀이도 아래 링크에 있으니 풀이를 참고하면 좋을 것 같다.

[4179번 불! 문제] | [4179번 불! 풀이]

 

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

 

 

코드

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

string graph[1001];
int w, h;
int visitedS[1001][1001];
int visitedF[1001][1001];
int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};
queue<pair<int, int>> qS, qF;
vector<int> ans;

void bfsS() {
  while (!qS.empty()) {
    int x = qS.front().first;
    int y = qS.front().second;
    qS.pop();
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if (nx < 0 || nx >= h || ny < 0 || ny >= w)
        continue;
      if (!visitedS[nx][ny] && graph[nx][ny] != '#') {
        visitedS[nx][ny] = visitedS[x][y] + 1;
        qS.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 >= h || ny < 0 || ny >= w)
        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);
  int t;
  cin >> t;
  while (t--) {
    ans.clear();
    cin >> w >> h;
    for (int i = 0; i < h; i++) {
      cin >> graph[i];
      for (int j = 0; j < w; j++) {
        visitedS[i][j] = 0;
        visitedF[i][j] = 0;
        if (graph[i][j] == '@') {
          qS.push({i, j});
          visitedS[i][j] = 1;
        }
        if (graph[i][j] == '*') {
          qF.push({i, j});
          visitedF[i][j] = 1;
        }
      }
    }
    bfsS();
    bfsF();
    for (int i = 0; i < h; i++) {
      if (visitedS[i][0] && (visitedS[i][0] < visitedF[i][0] || !visitedF[i][0]))
        ans.push_back(visitedJ[i][0]);
      if (visitedS[i][w - 1] && (visitedS[i][w - 1] < visitedF[i][w - 1] || !visitedF[i][w - 1]))
        ans.push_back(visitedJ[i][w - 1]);
    }
    for (int i = 0; i < w; i++) {
      if (visitedS[0][i] && (visitedS[0][i] < visitedF[0][i] || !visitedF[0][i]))
        ans.push_back(visitedJ[0][i]);
      if (visitedS[h - 1][i] && (visitedS[h - 1][i] < visitedF[h - 1][i] || !visitedF[h - 1][i]))
        ans.push_back(visitedJ[h - 1][i]);
    }
    if (ans.empty())
      cout << "IMPOSSIBLE\n";
    else
      cout << *min_element(ans.begin(), ans.end()) << '\n';
  }
  return 0;
}