[백준] 5427번: 불 (C++)

문제 링크

5427번: 불

---

BFS 응용 문제 중 하나입니다.

처음에 '상범이가 어떻게 이동하지?' 라는 생각으로 시간이 좀 걸렸습니다.

백트래킹, 최단거리 등을 생각하면서 고민했는데, 결국엔 BFS로 다 해결할 수 있었습니다.

풀이

불과 상범이의 queue를 각각 만들어서 서로의 거리를 비교하면 됩니다.

1. 불의 Queue와 Vst(방문배열), 상범이의 Queue와 Vst(방문배열)을 각각 만들어서 큐에 넣어줍니다.
2. 불은 간단하게 BFS로 상하좌우로 퍼지게 하면서, 방문배열에 거리를 적어둡니다.
3. 상범이를 움직이면서 방문배열에 거리를 적어둡니다. 그리고 불의 방문배열에 있는 거리와 비교하여 상범이의 거리가 더 작으면 상범이를 상하좌우로 움직입니다.
4. 상범이가 맵의  끝으로 나오면 성공이고, 나오지 못하면 실패입니다.

풀이코드

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

#define endl "\n"

string building[1001];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int firevst[1001][1001];
int sangvst[1001][1001];

void solve() {
  int t;
  cin >> t;
  while (t--) {
    int w, h;
    cin >> w >> h;
    for (int i = 0; i < h; i++) {
      fill(firevst[i], firevst[i] + w, INT_MAX);
      fill(sangvst[i], sangvst[i] + w, -1);
    }
    queue<pair<int, int>> fireQ;
    queue<pair<int, int>> sangQ;
    for (int i = 0; i < h; i++) {
      cin >> building[i];
      for (int j = 0; j < w; j++) {
        if (building[i][j] == '*') {
          fireQ.push({i, j});
          firevst[i][j] = 0;
        } else if (building[i][j] == '@') {
          sangQ.push({i, j});
          sangvst[i][j] = 0;
        }
      }
    }

    // 불이 번지고
    while (!fireQ.empty()) {
      auto [x, y] = fireQ.front(); fireQ.pop();
      for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 0 or nx >= h or ny < 0 or ny >= w) continue;
        if (building[nx][ny] == '#' or building[nx][ny] == '*') continue;
        if (firevst[nx][ny] != INT_MAX) continue;
        fireQ.push({nx, ny});
        firevst[nx][ny] = firevst[x][y] + 1;
      }
    }

    int time = 0;
    bool escape = false;
    
    // 상범이가 이동
    while (!sangQ.empty()) {
      auto [x, y] = sangQ.front(); sangQ.pop();
      for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 0 or nx >= h or ny < 0 or ny >= w) {
          escape = true;
          time = sangvst[x][y] + 1;
          break;
        }
        if (building[nx][ny] == '#' or building[nx][ny] == '*') continue;
        if (firevst[nx][ny] <= sangvst[x][y] + 1) continue;
        if (sangvst[nx][ny] >= 0) continue;
        sangQ.push({nx, ny});
        sangvst[nx][ny] = sangvst[x][y] + 1;
      }
      if (escape) break;
    }

    if (escape) cout << time << endl;
    else cout << "IMPOSSIBLE" << endl;
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

`fireVst`와 `sangVst`의 원활한 비교를 위해서(66번줄 참고) `fireVst`는 초기에 무한 값으로, `sangVst`는 초기에 -1로 초기화를 했습니다.

배운점

• 두 개의 큐를 이용하여 거리 비교를 통해 문제를 해결하는 방법을 배울 수 있었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!