[백준] 4179. 불!
2023. 12. 28. 00:12ㆍCS/Algorism
https://www.acmicpc.net/problem/4179
bfs 문제인데 이 문제를 풀며 주의할 점이 몇가지 있다.
- 논리적으로 불과 지훈이 동시에 이동해야 한다. 따라서 코드 상으로 불과 지훈이 순차적으로 한 번씩 이동해야 하는데, 둘 중에 불을 먼저 이동시켜야 한다. 불이 먼저 이동해서 불이 번지면, 지훈이가 불이 있는 곳을 피해서 이동해야 하기 때문이다.
- 불을 한 번 이동시킬 때는 fireQue의 사이즈만큼 이동을 처리해주어야 한다. 그래야 그래프에 있는 번져야 하는 불들이 각각 모두 번지게 되는 것이다. 그리고 불이 번지면 그 위치의 값을 "F"로 변경해주어야 한다.
- 마찬가지로 지훈이를 이동시킬 때도 jihoonQue의 사이즈만큼 이동을 처리해주어야 한다.
- 지훈이가 이동할 수 없는 경우에는 continue로 pass하고, 이동할 수 있으면 그 위치를 johoonQue에 넣어준다. 따라서 지훈이가 더이상 이동할 수 없으면, 즉 jihoonQue가 비면 탈출에 실패한 것이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// 시간복잡도: O(V+E) = 10,000 * 10,000 + 4 * 10,000 * 10,000 = 500,000,000
public class Main {
static int r;
static int c;
static String[][] map;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static Queue<Position> jihoonQue = new LinkedList<>();
static Queue<Position> fireQue = new LinkedList<>();
static boolean[][] jihoonVisited;
static int answer = 0; // 탈출할 수 있는 가장 빠른 시간
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
map = new String[r][c];
jihoonVisited = new boolean[r][c];
for (int i = 0; i < r; i++) {
String[] arr = br.readLine().split("");
for (int j = 0; j < c; j++) {
map[i][j] = arr[j];
if (map[i][j].equals("J")) {
jihoonQue.add(new Position(i, j));
jihoonVisited[i][j] = true;
}
if (map[i][j].equals("F")) {
fireQue.add(new Position(i, j));
}
}
}
bfs();
}
private static void bfs() {
// 지훈이 이동할 수 있을 때까지 반복
while (!jihoonQue.isEmpty()) {
// 불 이동
int fireQueSize = fireQue.size();
for (int i = 0; i < fireQueSize; i++) {
Position fire = fireQue.poll();
for (int j = 0; j < 4; j++) {
int ny = fire.y + dy[j];
int nx = fire.x + dx[j];
// 그래프 범위를 넘어가면 pass
if (nx < 0 || nx >= c || ny < 0 || ny >= r) {
continue;
}
// 벽이면 번질 수 없고, 이미 불이면 번질 필요 없으므로 pass
if (map[ny][nx].equals("#") || map[ny][nx].equals("F")) {
continue;
}
// 불 번지기
map[ny][nx] = "F";
fireQue.add(new Position(ny, nx));
}
}
// 지훈 이동
int jihoonQueSize = jihoonQue.size();
for (int i = 0; i < jihoonQueSize; i++) {
Position jihoon = jihoonQue.poll();
for (int j = 0; j < 4; j++) {
int ny = jihoon.y + dy[j];
int nx = jihoon.x + dx[j];
// 탈출했으면 끝내기
if (nx < 0 || nx >= c || ny < 0 || ny >= r) {
System.out.println(answer + 1);
return;
}
// 이미 방문했었거나 불이 있거나 벽이면 pass
if (jihoonVisited[ny][nx] || map[ny][nx].equals("F") || map[ny][nx].equals("#")) {
continue;
}
// 지훈 이동하기
jihoonVisited[ny][nx] = true;
jihoonQue.add(new Position(ny, nx));
}
}
answer++;
}
// 탈출하지 못하고 더이상 이동이 불가하면 탈출 실패
System.out.println("IMPOSSIBLE");
}
static class Position {
int y, x;
public Position(int y, int x) {
this.y = y;
this.x = x;
}
}
}
'CS > Algorism' 카테고리의 다른 글
[백준] 1697. 숨바꼭질 (0) | 2023.12.29 |
---|---|
[백준] 1541. 잃어버린 괄호 (0) | 2023.12.29 |
[백준] 7576. 토마토 (1) | 2023.12.26 |
[백준] 2178. 미로 탐색 (0) | 2023.12.26 |
[백준] 1926. 그림 (1) | 2023.12.26 |