[BOJ] 4179 : 불!

Drakk·2021년 8월 7일

BFS C boj 그래프이론 백준 알고리즘

알고리즘 문제풀이

목록 보기

20/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.

#: 벽

.: 지나갈 수 있는 공간

J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)

F: 불이 난 공간
J는 입력에서 하나만 주어진다.

🧺출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

🔋예제 입출력

🔮예제 입력1
4 4
####
#JF#
#..#
#..#

🔮예제 출력1
3

💉문제 분석

🔋분류

그래프이론, DFS, BFS

🔋난이도

골드IV

💉문제 풀이

🔋해법

저가 bfs문제를 여러번 풀어보면서 알아낸것중하나가 bfs를 접근하는것도 여러가지가 있다는것입니다.

이 문제는 bfs를 한칸씩 전진하면서 진행하는게 핵심입니다.
먼저 이러한 유형의 문제는 불을 먼저움직이고, 그다음 사람을 움직이면됩니다.

나머지는 그냥 생각했던대로 풀었습니다.
queue에 들어간 사이즈만큼만 실행해주는게 핵심이죠.
그리고 배열밖으로 나가면 결과값을 반환해주면됩니다.

🔋소스코드

#include <bits/stdc++.h>

constexpr int INF = 1e9 + 7;
constexpr int MAX = 1001;

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

std::string adj[MAX];
bool visit[2][MAX][MAX];
std::queue<std::pair<int, int>> J, F;

int bfs(int R, int C) {
	int result = 0;

	while (!J.empty()) {
		int fsize = F.size();
		for (std::size_t k = 0; k < fsize; ++k) {
			int y = F.front().first;
			int x = F.front().second;
			F.pop();

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

				if (nx >= 0 && ny >= 0 && nx < C && ny < R) {
					if (!visit[0][ny][nx] && (adj[ny][nx] == '.' || adj[ny][nx] == 'J')) {
						adj[ny][nx] = 'F';
						visit[0][ny][nx] = true;
						F.push({ ny, nx });
					}
				}
			}
		}

		int jsize = J.size();
		for (std::size_t k = 0; k < jsize; ++k) {
			int y = J.front().first;
			int x = J.front().second;
			J.pop();

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

				if (nx < 0 || ny < 0 || nx >= C || ny >= R) return result + 1;

				if (nx >= 0 && ny >= 0 && nx < C && ny < R) {
					if (!visit[1][ny][nx] && adj[ny][nx] == '.') {
						visit[1][ny][nx] = true;
						J.push({ ny, nx });
					}
				}
			}
		}

		++result;
	}

	return -1;
}

int main() {
	std::cin.tie(0);
	std::cout.tie(0);
	std::ios_base::sync_with_stdio(0);

	int R, C;
	std::cin >> R >> C;

	for (int i = 0; i < R; ++i) {
		std::cin >> adj[i];

		for (int j = 0; j < C; ++j) {
			if (adj[i][j] == 'J') J.push({ i, j });
			else if (adj[i][j] == 'F') F.push({ i, j });
		}
	}

	int result = bfs(R, C);
	if (result == -1) std::cout << "IMPOSSIBLE";
	else std::cout << result;
}