백준 4179번 불! (Java)

devyumi·2025년 1월 26일

알고리즘

Java

목록 보기

13/14

문제

해결 과정

1. 2개의 BFS 사용

이번 문제에서는 불과 지훈 모두 1분마다 이동하기 때문에 각각 BFS 알고리즘을 적용하여 문제를 풀었다.

알고리즘을 풀어 설명하면 다음과 같다.

1) 미로를 지훈 배열과 불 배열에 각각 저장한다.
1-1) 지훈의 위치가 이미 가장자리라면 곧바로 정답을 도출한다.
1-2) 그렇지 않으면 불과 지훈의 위치를 기준으로 BFS 알고리즘을 사용한다.

가령, 다음과 같은 입력값들은 바로 탈출할 수 있다.
4 4
J...
....
F.F.
FFFF

2 2
JF
FF

3 3
J#F
#FF
FFF

2) 다음 조건을 모두 만족하면 최소 시간을 업데이트 한다.
2-1) 이동 시간이 불 > 지훈일 것 (지훈이가 불에 타기 전에 이동해야 한다.)
2-2) 지훈의 위치가 가장자리일 것
2-3) 최소 시간일 것

최종 주요 코드

for (int i = 0; i < r; i++) {
	String[] str = br.readLine().split("");
	for (int j = 0; j < c; j++) {
		person[i][j] = str[j];
		fire[i][j] = person[i][j];

		if (fire[i][j].equals("J")) {
			personQ.offer(new int[]{i, j});
			person[i][j] = "0";
			fire[i][j] = ".";
			point[0] = i;
			point[1] = j;
		} else if (fire[i][j].equals("F")) {
			fireQ.offer(new int[]{i, j});
			fire[i][j] = "0";
			person[i][j] = ".";
		}
	}
}


//이미 사람의 위치가 가장자리라면 탐색하지 않고 정답 도출
if (point[0] == r - 1 || point[1] == c - 1 || point[0] == 0 || point[1] == 0) {
	System.out.print(1);
} else {
	bfs(fire, fireQ);
	bfs(person, personQ);
	calTime(person, fire, point);
}
br.close();


private static void calTime(String[][] person, String[][] fire, int[] point) {
//R, C의 크기가 최대 1000이기 때문에 다음과 같이 초기화
	int answer = 1001;

	//가장자리면서 최소 시간일 때만 업데이트
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (person[i][j].equals("#") || person[i][j].equals(".")) {
				continue;
			}

			if (fire[i][j].equals("#") || fire[i][j].equals(".")) {
				if (answer > Integer.parseInt(person[i][j])) {
					if (i == r - 1 || j == c - 1 || i == 0 || j == 0) {
						answer = Integer.parseInt(person[i][j]);
						point[0] = i;
						point[1] = j;
					}
				}
			} else {
				if (Integer.parseInt(fire[i][j]) > Integer.parseInt(person[i][j])) {
					if (answer > Integer.parseInt(person[i][j])) {
						if (i == r - 1 || j == c - 1 || i == 0 || j == 0) {
							answer = Integer.parseInt(person[i][j]);
							point[0] = i;
							point[1] = j;
						}
					}
				}
			}
		}
	}

	if (point[0] == r - 1 || point[1] == c - 1 || point[0] == 0 || point[1] == 0) {
		System.out.print(answer + 1);
	} else {
		System.out.print("IMPOSSIBLE");
	}
}