[BOJ/5427/C++] 불

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

문제

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

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

문제조건

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

입출력 조건

• 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
• 각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
• 다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
  '.': 빈 공간
  '#': 벽
  '@': 상근이의 시작 위치
  '*': 불

풀이

초기화를 꼭 까먹지 말아야하는 문제이다. BFS 문제를 풀다보면, 여러가지 TEST CASE를 주는 문제가 있는데, 그 문제들은 꼭 초기화를 해주어야 한다.

방문배열을 초기화 하는 방법

방문배열은 bool타입으로 선언을 많이 하기 때문에, 아래처럼 초기화할 수 있다. sizeof(visited)를 하면, bool은 1byte이기 때문에 다른 자료형처럼 해당 자료형의 크기로 나눠줄 필요가 없다.

memset(visited,false,sizeof(visited))

Queue를 초기화 하는 방법

• Queue는 vector와 다르게 clear명령어가 없다. 따라서, 빈 큐로 교체해주면 된다.

Queue<int> empty;
swap(기존 큐, empty);

그리고 이 문제는 Queue의 Size를 이용해서 반복한다는 특이한 점이 있다. Queue의 사이즈를 이용하는 문제들은, 2개 이상의 요소가 있을 때, 하나씩 진행하고 싶을 때 Queue의 사이즈를 이용할 수 있다.
예를들어, 위 문제에서는 불이 퍼지고 -> 상근이 이동시키고 -> 불이 퍼지고 -> 상근이 이동시키고 등 시간에 따라 사건이 진행되는 경우 Queue의 사이즈를 이용할 수 있다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define X first
#define Y second
using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int N, M, T, Time;
char board[1001][1001];
bool visited[1001][1001];

queue<pair<int, int>> Fire_Q;
queue<pair<int, int>> Person_Q;

bool outOfRange(int x, int y)
{
  return (x < 0 || x >= N || y < 0 || y >= M);
}
void init()
{
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      cin >> board[i][j];
    }
  }
  // 답 초기화
  Time = 0;
  // 방문배열 초기화
  memset(visited, false, sizeof(visited));
  // 큐 초기화
  queue<pair<int, int>> empty;
  swap(Fire_Q, empty);
  queue<pair<int, int>> empty2;
  swap(Person_Q, empty2);
}

void find_Elements()
{
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      if (board[i][j] == '@')
      {
        visited[i][j] = true;
        board[i][j] = '.';
        Person_Q.push({i, j});
      }
      else if (board[i][j] == '*')
      {
        visited[i][j] = true;
        Fire_Q.push({i, j});
      }
    }
  }
}

void solve()
{
  // 상근이의 움직임이 멈출때 까지,
  while (!Person_Q.empty())
  {
    Time++;
    int FireQ_size = Fire_Q.size();
    int PersonQ_size = Person_Q.size();
    // 불 먼저 -> 그 다음 상근이 .
    while (FireQ_size--)
    {
      pair<int, int> cur = Fire_Q.front();
      Fire_Q.pop();
      for (int dir = 0; dir < 4; dir++)
      {
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        if (outOfRange(nx, ny))
          continue;
        if (board[nx][ny] == '#' || visited[nx][ny])
          continue;
        visited[nx][ny] = true;
        Fire_Q.push({nx, ny});
      }
    }
    while (PersonQ_size--)
    {
      pair<int, int> cur = Person_Q.front();
      Person_Q.pop();
      for (int dir = 0; dir < 4; dir++)
      {
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        if (outOfRange(nx, ny))
        {
          cout << Time << '\n';
          return;
        }
        // 벽인 곳 ,이미 불이 퍼진 곳 or 내가 방문한 곳
        if (board[nx][ny] == '#' || visited[nx][ny])
          continue;
        visited[nx][ny] = true;
        Person_Q.push({nx, ny});
      }
    }
  }
  cout << "IMPOSSIBLE" << '\n';
  return;
}
int main()
{
  fastio;
  cin >> T;
  while (T--)
  {
    cin >> M >> N;
    init();
    find_Elements();
    solve();
  }
  return 0;
}