JArchive 프로그래밍 일기

문제

불! 백준 4179 c++

"맞았습니다."코드 

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

// 4179 불!
int R, C;
char m[1002][1002];
bool vis[1002][1002];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool exitflag = false;
queue<pair<int,int>> qf; // {좌표}
queue<pair<int,int>> qh; // {좌표}

bool checkrange(int i, int j){
  return (i >= 0 && i < R && j >= 0 && j < C);
}

int bfs(){

  int time = 0;

  while(!qh.empty() && !exitflag){
    time++;
    int hsize = qh.size();
    int fsize = qf.size();

    while(fsize--){
      int cx = qf.front().X;
      int cy = qf.front().Y;
      qf.pop();

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

        if(!checkrange(nx, ny) || m[nx][ny] == '#' || vis[nx][ny]) continue;
        m[nx][ny] = 'F';
        vis[nx][ny] = true;
        qf.push({nx,ny});
      }
    }

    while(hsize--) {
      int cx = qh.front().X;
      int cy = qh.front().Y;
      qh.pop();

      if (cx == 0 || cy == 0 || cx == (R-1) || cy == (C-1)) {
        exitflag = true;
        break;
      }

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

        if (!checkrange(nx, ny) || m[nx][ny] == '#' || vis[nx][ny]) continue;
        vis[nx][ny] = true;
        qh.push({nx,ny});
      }
    }
  }
  return time;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> R >> C; // 행, 열
  for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){
      cin >> m[i][j];
      if(m[i][j] == 'J') {
        qh.push({i, j}); m[i][j] = '.'; vis[i][j] = true;
      }
      else if (m[i][j] == 'F') {
        qf.push({i, j}); vis[i][j] = true;
      }
      else if (m[i][j] == '#') vis[i][j] = true;
    }
  }

  int answer = bfs();

  if(exitflag){
    cout << answer;
  }else{
    cout << "IMPOSSIBLE";
  }

  return 0;
}

리뷰 

불과 지훈이의 큐 

불의 시작점이 여러개가 주어지는 경우가 있다는걸 간과하고 처음에 헤맸다.

불의 시작점은 qf에 모두 넣었다. 

불이 번지면 맵에 F로 표시했다. 

지훈이의 시작점 J는 qh에 넣는다. 

J는 불이 여기로 이동할 수 있는 칸이니까 . 으로 바꿔서 입력받도록 했다. 

불과 지훈이의 이동 순서 

만약 점이 1개라면, 불의 이동과 지훈이의 이동이 동시라고 했을 때 지훈이는 탈출하지 못한다. 

따라서 불이 1칸 번지고, 지훈이가 1칸 이동하는 순서로 이동시켜야 한다. 불 1번, 지훈이 1번 이렇게 갈아서 이동시켜야 한다.  

지훈이가 탈출하는 것이 중요하니까 지훈이가 이동할 수 있는 곳은 모두 이동해봐야 한다. 

그래서 가장 바깥의 while문의 조건은 지훈이 큐 qh가 빌 때까지 돌린다. 

탈출 지점의 조건

맵의 가장자리에 가야 지훈이가 탈출한다.  

exitflag를 둬서 탈출하면 가장 바깥의 while 문을 탈출하도록 했다. 

pop 했을 때 좌표가 행이 0 또는 마지막행이면 된다. 열이 0이 되거나 마지막 열이면 탈출이다.