[백준] 4179번: 불!

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

4179번: 불!

으

으

으

 

왕바보!

가장 빠른 탈출 시간을 출력하면 되기 때문에 BFS를 쓰면 쉬운 문제처럼 보이나 은근 까다로웠던 문제이다.

여기서 핵심은 불의 확산이다.

단계별로 불을 확산해야 하는데, 처음에는 한 배열에 불로만 표시하려고 불 여부만 판단하고 이를 상하좌우로 확산했다.

그런데 현재 단계와 이전 단계들의 구분이 없어져서, 결국 한 단계만에 모든 빈칸에 불이 확산되는 꼴이 되어버렸다.\

 

그래서 이를 개선하기 위해 별도의 2차원 배열을 이용해서 이전 단계와 새로운 단계를 구분하였다.

이렇게 풀다보니 매번 배열을 탐색해야하다보니 시간초과가 발생했다.

 

이를 개선하기 위해 서치한 결과, 불이라는 표시를 F로 하지 않고, 단계를 표시하면 직전 단계에 대해서만 확산을 수행할 수 있다.

그래서 전반적으로 char 타입의 배열에서 int 형 배열로 변형하였다.

 

편리한 연산을 위해

# → -1

. → 0

F → 양수

 

아래와 같이 이전 단계에 불이 있고, 현재 도달한 위치가 빈칸인 경우에만 확산 처리를 한다.

if(map[i][j] > 0 && map[i][j] == t) {
    for(int d = 0;d < 4;d++) {
        int ni = i + dr[d];
        int nj = j + dc[d];

        if(inside(ni,nj) && map[ni][nj] == 0)
            map[ni][nj] = map[i][j] + 1;
    }
}

#include <iostream>
#include <tuple>
#include <vector>
#include <queue>
using namespace std;
int R, C;
queue<tuple<int,int,int>> q;

int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
int answer = -1;
bool inside(int r, int c) {
	return r >= 0 && r < R && c >= 0 && c < C; 
}

void bfs(int row, int column, vector<vector<int>> &map, vector<vector<bool>> &visited) {
	int turn = 0;
	q.push({row, column, 1});
	visited[row][column] = true;

	while(!q.empty()) {
		auto value = q.front();
		int r = get<0>(value);
		int c = get<1>(value);
		int t = get<2>(value);

		q.pop();

		if(answer != -1) break;


		if(t > turn) {

			while(t != turn) {
				for(int i = 0;i < R;i++) {
					for(int j = 0;j < C;j++) {
						if(map[i][j] > 0 && map[i][j] == t) {
							for(int d = 0;d < 4;d++) {
								int ni = i + dr[d];
								int nj = j + dc[d];

								if(inside(ni,nj) && map[ni][nj] == 0)
									map[ni][nj] = map[i][j] + 1;
							}
						}
					}
				}
				turn++;
			}
		}

		for(int d = 0;d < 4;d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];

			if(inside(nr, nc) && map[nr][nc] == 0 && !visited[nr][nc]) {
				q.push({nr, nc, t + 1});
				visited[nr][nc] = true;
			}
			else if(!inside(nr, nc)){
				answer = t;
				break;
			}
		}
	}
}
int main() {
	int starting_r, starting_c;
	cin >> R >> C;
	vector<vector<int>> map(R, vector<int>(C));
	vector<vector<bool>> visited(R, vector<bool>(C, false));
	for(int i = 0;i < R;i++) {
		for(int j = 0;j < C;j++) {
			char c;
			cin >> c;
			if(c == 'J') {
				starting_r = i;
				starting_c = j;
				map[i][j] = 0;
			}
			else if(c == '#') {
				map[i][j] = -1;
			}
			else if(c == 'F') {
				map[i][j] = 1;
			}
			else if(c == '.') {
				map[i][j] = 0;
			}
		}
	}

	bfs(starting_r, starting_c, map, visited);

	if(answer == -1) {
		cout << "IMPOSSIBLE" << '\n';
	}
	else {
		cout << answer << '\n';
	}
}