문제링크 : https://www.acmicpc.net/problem/4179
접근 과정 :
- 위 문제와 거의 같은 문제이다.
- 불을 퍼뜨리면서, 지훈이의 위치로 BFS 탐색 해주면 된다.
- 다만, 지훈이가 움직이는 위치에 방문체크를 해서 Queue에 중복저장되지 않게 해야 한다.
- 안그러면 메모리초과가 발생할 것이다.
소스 코드 및 결과 :
package BOJ;
/*
불!
*/
import java.io.*;
import java.util.*;
public class BOJ4179 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
char[][] map = new char[R][C];
Queue<int[]> jihun = new LinkedList<>();
Queue<int[]> fire = new LinkedList<>();
boolean[][] visit = new boolean[R][C];
for (int i = 0; i < R; i++) {
map[i] = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
if (map[i][j] == 'J') {
jihun.add(new int[] { i, j });
map[i][j] = '.';
visit[i][j] = true;
} else if (map[i][j] == 'F') {
fire.add(new int[] { i, j });
}
}
}
int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
int count = 0;
loop: while (true) {
count++;
int size = fire.size();
while (size-- > 0) {
int[] f = fire.poll();
for (int i = 0; i < 4; i++) {
int nr = f[0] + move[i][0];
int nc = f[1] + move[i][1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || map[nr][nc] != '.') {
continue;
}
map[nr][nc] = 'F';
fire.add(new int[] { nr, nc });
}
}
size = jihun.size();
while (size-- > 0) {
int[] j = jihun.poll();
for (int i = 0; i < 4; i++) {
int nr = j[0] + move[i][0];
int nc = j[1] + move[i][1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
System.out.println(count);
break loop;
}
if (visit[nr][nc] || map[nr][nc] != '.') {
continue;
}
visit[nr][nc] = true;
jihun.add(new int[] { nr, nc });
}
}
if (jihun.isEmpty()) {
System.out.println("IMPOSSIBLE");
break;
}
}
}
}
P.S
DFS, BFS등의 탐색을 할 경우에는 역시나 방문체크를 해서 필요없는 경우의 수 또는 연산을 줄이는 게 중요한 것 같다.
'Algorithm' 카테고리의 다른 글
[백준 Gold 2] 1766 문제집 - Java (0) | 2022.01.13 |
---|---|
[백준 Gold 3] 14890 경사로 - Java (0) | 2022.01.12 |
[백준 Silver 5] 11728 배열 합치기 - Java (0) | 2022.01.12 |
[백준 Silver 4] 1244 스위치 켜고 끄기 - Java (0) | 2022.01.12 |
[백준 Gold 1] 2357 최솟값과 최댓값 - Java (0) | 2022.01.10 |