BOJ_4179_불!

이 글은 공부하는 "학생"의 글입니다. 오류가 있음을 알려드립니다. 혹시 오류를 발견하실 경우, 댓글 남겨주시면 정말 감사드리겠습니다:)

오늘도 이어서 BFS를 풀어보고자 합니다. BFS는 참 아이러니 합니다. 공부를 그렇게 해도, 조금만 비틀면 헤깔리니, 문제 수로 눌러서 개념을 머리에 박는 수밖에. 뜬금없지만, 저는 공부스타일도 BFS인 것 같습니다. 전반적인 지식의 흐름을 다 알고 그 다음, DFS로 진행합니다. 뭔가 쭉 흐름을 알고 시작하는게 마음 편하더군요. 여튼! 오늘 풀 불 문제 또한, 저 번 토마토 문제처럼 여러 곳에서 BFS가 시작하는 문제입니다. 단, BFS를 시작하는 지점마다의 차이가 조금 있는데요, 같이 봐보시죠!

문제출처 : https://www.acmicpc.net/problem/4179

접근방법

• 미로의 행렬이 입력값으로 주어진다.
  -> grid 문제임을 확인할 수 있다.
• 불이 매분마다 수평또는 수직으로 네 방향 확산된다는 표현이 있다.
  -> BFS를 활용해야겠다.
• 지훈이는 미로의 가장자리에 접한 공간에서 탈출가능
  -> 경계조건에서 지훈이가 탈출한 로직을 구현해야겠다.
• 입력값이 string으로 주어진다. 2차원 배열이긴 한데, string으로 2차를 채워야겠다.
• 문제에 조건이 좀 부족했는데, 지훈이는 한 명이지만, 불은 여러 곳에서 날 수 있다.
• 먼저 불로 BFS를 돌리고, 해당 vis값과 지훈이의 BFS값을 비교하면서 지훈이의 BFS를 넓혀나가는 식으로 하자.
  -> 지훈이는 뻗어나갈 때, 불과 동시에 혹은 불보다 느리게 갈 경우, 해당 지점으로는 갈 수 없기 때문에
• 입력으로 주어지는 행(R)과 열(C)가 1이상 1000이하이다. BFS로 100만이 나온다.
  -> 시작복잡도를 보았을 때, O(R*C)라 100만으로 해결가능하다.

시간복잡도 : O(R*C) -> O(N) : 100만

#include<iostream>
#include<queue>
#define MX_I 987654321
using namespace std;

int r, c;
string arr[1002];
int dist_j[1002][1002];
int dist_f[1002][1002];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int ret = MX_I;	// 지훈이의 탈출 최소 시간

int main() {
	cin >> r >> c;
	string S;
	queue<pair<int, int>> Qj;
	queue<pair<int, int>> Qf;
	for (int i = 0; i < r; i++) {
		fill(dist_j[i], dist_j[i] + c, -1);
		fill(dist_f[i], dist_f[i] + c, -1);
	}
	for (int i = 0; i < r; i++) {
		cin >> S;
		arr[i] = S;
		for (int j = 0; j < c; j++) {
			if (S[j] == 'J') {
				Qj.push({ i, j });
				dist_j[i][j] = 0;
			}
			else if (S[j] == 'F') {
				Qf.push({ i, j });
				dist_f[i][j] = 0;	// 0이상일 경우 visited이다.
			}
		}
	}
	
	// 불의 영역으로 먼저 bfs를 돌린다.
	while (!Qf.empty()) {
		auto curr = Qf.front(); Qf.pop();
		for (int i = 0; i < 4; i++) {
			int nx = curr.first + dx[i];
			int ny = curr.second + dy[i];
			if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			if (arr[nx][ny] == '#' || dist_f[nx][ny] != -1) continue;
			dist_f[nx][ny] = dist_f[curr.first][curr.second] + 1;
			Qf.push({ nx, ny });
		}
	}

	// 이제 지훈이로 bfs를 돌린다.
	while (!Qj.empty()) {
		auto curr = Qj.front(); Qj.pop();
		for (int i = 0; i < 4; i++) {
			int nx = curr.first + dx[i];
			int ny = curr.second + dy[i];
			// 탈출할 수 있는 순간	-> queue가 거리순으로 채워지기 때문에 이 지점 들리면 함수 종료
			if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
				cout << dist_j[curr.first][curr.second] + 1;
				return 0;
			}
			if (arr[nx][ny] == '#' || dist_j[nx][ny] != -1) continue;
			// 다음 점에서 불이 먼저, 혹은 동시에 점거 했어도 이동할 수 없다.
			// dist_f[nx][ny]를 붙여준 것은 불이 점령한 지점만 체크해야하므로.
			if (dist_f[nx][ny] != -1 && dist_f[nx][ny] <= dist_j[curr.first][curr.second] + 1) continue;
			dist_j[nx][ny] = dist_j[curr.first][curr.second] + 1;
			Qj.push({ nx, ny });
		}
	}
	cout << "IMPOSSIBLE";
	return 0;
}

추가적으로 알아야할 부분

• BFS에서는 Queue가 채워질 때, 거리 순으로 채워지게 된다.
• 예를 들어 불이 난 지점 부터 '000111122222' 이와 같이 채워지는 것이다.