문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

  • char형 배열에 맵이 주어진다.
    • ., #, J, F는 각각 지나갈 수 있는 공간, 벽, 초기위치, 불이 난 공간
    • J는 입력에서 하나만 주어진다.
  • 불은 1초마다 상,하,좌,우로 퍼지게 된다.
  • 지훈이와 불은 벽을 통과할 수 없다.
  • 가장 빠른 탈출 시간을 출력하고, 탈출이 불가능하면 IMPOSSIBLE 출력



2. 알고리즘 설계

  • 지훈이의 위치를 큐에 넣고 BFS
  • 단, BFS의 마지막 부분에 불을 확산시키기 위한 로직 필요



3. 로직

  • 지훈이의 위치를 저장하고 큐에 넣어준다.
    • 지훈이의 위치는 .으로 변환
  • 지훈이의 위치에서 상,하,좌,우 중 갈 수 있는 모든 칸을 큐에 넣는다.
    • 여기서 중요한 건 지훈이가 이동 가능한 모든 위치를 한번에 갱신시켜야 한다.
      • size()를 이용해 현재 저장된 모든 위치를 한번에 갱신
    while (!q.empty()) {
      int q_sz = q.size();
      while (q_sz--) {....}
}

  • 불을 확산시키는 것 또한 size()를 이용해 4방향을 전부 확산시켜야 한다.

    void spread(void) 
{
    int sz = fire.size();
    while (sz--) {...}
}


4. 전체 코드

#include <iostream>
#include <queue>
#include <string>
using namespace std;
using pii = pair<int, int>;

typedef struct {
	int y, x, w;
}pos;

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

const int SZ = 1001;

char map[SZ][SZ];
bool visited[SZ][SZ];
int r, c;

queue<pii> fire;
pos src;

void spread(void) 
{
	int sz = fire.size();
	while (sz--) {
		pii cur = fire.front();
		fire.pop();

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.first + dy[dir];
			int nx = cur.second + dx[dir];

			if (ny < 0 || nx < 0 || ny >= r || nx >= c)
				continue;
			if (map[ny][nx] == '.') {
				fire.push({ ny, nx });
				map[ny][nx] = 'F';
			}
		}
	}
}

int escape(void) 
{
	queue<pos> q;
	q.push(src);
	visited[src.y][src.x] = true;

	while (!q.empty()) {
		int q_sz = q.size();
		while (q_sz--) {
			pos cur = q.front();
			q.pop();

			if (map[cur.y][cur.x] == 'F')
				continue;

			if (cur.y == r - 1 || cur.y == 0 || cur.x == c - 1 || cur.x == 0)
				return cur.w + 1;

			for (int dir = 0; dir < 4; dir++) {
				int ny = cur.y + dy[dir];
				int nx = cur.x + dx[dir];

				if (ny < 0 || nx < 0 || ny >= r || nx >= c)
					continue;
				if (visited[ny][nx] || map[ny][nx] != '.')
					continue;

				q.push({ ny, nx, cur.w + 1 });
				visited[ny][nx] = true;
			}
		}
		spread();
	}

	return -1;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> r >> c;
	for (int y = 0; y < r; y++) {
		for (int x = 0; x < c; x++) {
			cin >> map[y][x];

			if (map[y][x] == 'J') {
				src = { y,x,0 };
				map[y][x] = '.';
			}
			if (map[y][x] == 'F')
				fire.push({ y,x });
		}
	}

	int res = escape();
	if (res < 0) cout << "IMPOSSIBLE";
	else cout << res;

	return 0;
}


5. 소감

  • queue의 size()를 통해, 현재 저장된 모든 위치의 상,하,좌,우를 고려하는 문제
  • 핵심은 동시에 갱신시키는 것