π₯ λ°±μ€ 4179λ² λΆ! (BFS νμ΄)
π₯ λ°±μ€ 4179λ² - λΆ! (BFS νμ΄)
π 1. λ¬Έμ μ€λͺ
μ§ν(J
)μ΄κ° λΆ(F
)μ΄ λ λ―Έλ‘μμ νμΆνλ λ¬Έμ μ
λλ€.
λΆ(F
)μ λμμ νΌμ§κ³ , μ§ν(J
)μ΄λ ν μΉΈμ© μ΄λν μ μμ΅λλ€.
λ²½(#
)μ μ΄λν μ μκ³ , μ§νμ΄κ° λ―Έλ‘μ κ°μ₯μ리μ λλ¬νλ©΄ νμΆν μ μμ΅λλ€.
π 2. μ λ ₯ λ° μΆλ ₯ μμ
πΉ μ λ ₯ μμ
4 4
####
#JF#
#..#
#..#
πΉ μΆλ ₯ μμ
3
π μ€λͺ
J
(μ§ν)λ (1,2)μμ μμF
(λΆ)λ (1,1)μμ μμ- λΆμ λμμ νμ°λκ³ , μ§νμ΄λ λΆλ³΄λ€ λ¨Όμ λμ°©νλ©΄ νμΆ κ°λ₯
π 3. ν΄κ²° λ°©λ² (BFS)
μ΄ λ¬Έμ λ μ΅λ¨ κ²½λ‘ νμ λ¬Έμ μ΄λ―λ‘,
BFS(λλΉ μ°μ νμ, Breadth-First Search)λ₯Ό μ¬μ©ν΄μΌ ν©λλ€.
πΉ ν΅μ¬ λ‘μ§
- λΆ(
F
)κ³Ό μ§ν(J
)μ κ°κ° BFS νμ μ μ₯ - λΆ(
F
)μ΄ λ¨Όμ νμ°, κ·Έ ν μ§ν(J
)μ΄ μ΄λ - μ§ν(
J
)μ΄ λ―Έλ‘μ κ°μ₯μ리μ λλ¬νλ©΄ μ¦μ νμΆ - μ§ν(
J
)μ΄ μ΄λν κ³³μ΄ μμΌλ©΄ βIMPOSSIBLEβ μΆλ ₯
π 4. Java μ½λ (BFS)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Back_4179 {
static int dX[] = {0, 0, 1, -1};
static int dY[] = {1, -1, 0, 0};
static int R, C;
static class Point {
int x, y, time;
Point(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
}
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());
char[][] map = new char[R][C];
Queue<Point> fires = new LinkedList<>();
Queue<Point> jihos = new LinkedList<>();
for (int i = 0; i < R; i++) {
String temp = br.readLine();
for (int j = 0; j < C; j++) {
map[i][j] = temp.charAt(j);
if (map[i][j] == 'F') {
fires.offer(new Point(i, j, 0)); // λΆ μμΉ μ μ₯
} else if (map[i][j] == 'J') {
jihos.offer(new Point(i, j, 0)); // μ§ν μμΉ μ μ₯
}
}
}
int result = bfs(map, jihos, fires);
System.out.println(result == -1 ? "IMPOSSIBLE" : result);
}
private static int bfs(char[][] map, Queue<Point> jihos, Queue<Point> fires) {
int[][] visited = new int[R][C];
while (!jihos.isEmpty()) {
// π₯ λΆ νμ°
int fireSize = fires.size();
for (int f = 0; f < fireSize; f++) {
Point fire = fires.poll();
for (int i = 0; i < 4; i++) {
int nx = fire.x + dX[i];
int ny = fire.y + dY[i];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
continue;
}
if (map[nx][ny] == '.' || map[nx][ny] == 'J') {
map[nx][ny] = 'F';
fires.offer(new Point(nx, ny, fire.time + 1));
}
}
}
// πββοΈ μ§ν μ΄λ
int jihoSize = jihos.size();
for (int j = 0; j < jihoSize; j++) {
Point jiho = jihos.poll();
for (int i = 0; i < 4; i++) {
int nx = jiho.x + dX[i];
int ny = jiho.y + dY[i];
// β
κ°μ₯μ리μ λλ¬νλ©΄ νμΆ
if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
return jiho.time + 1;
}
if (map[nx][ny] == '.' && visited[nx][ny] == 0) {
visited[nx][ny] = 1;
jihos.offer(new Point(nx, ny, jiho.time + 1));
}
}
}
}
return -1;
}
}
π 5. ν΅μ¬ μ½λ μ€λͺ
1οΈβ£ fires
νλ₯Ό μ¬μ©νμ¬ λΆ(F
) νμ°
int fireSize = fires.size();
for (int f = 0; f < fireSize; f++) {
Point fire = fires.poll();
for (int i = 0; i < 4; i++) {
int nx = fire.x + dX[i];
int ny = fire.y + dY[i];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
continue;
}
if (map[nx][ny] == '.' || map[nx][ny] == 'J') {
map[nx][ny] = 'F';
fires.offer(new Point(nx, ny, fire.time + 1));
}
}
}
β
ν λ²μ BFS λ¨κ³μμ λͺ¨λ λΆμ νμ°μν΄
β
λΆ(F
)μ΄ λ¨Όμ μ΄λνλλ‘ νμ¬ μ§ν(J
)μ μ΄λμ λ°©ν΄νλλ‘ μ€μ
2οΈβ£ jihos
νλ₯Ό μ¬μ©νμ¬ μ§ν(J
) μ΄λ
int jihoSize = jihos.size();
for (int j = 0; j < jihoSize; j++) {
Point jiho = jihos.poll();
for (int i = 0; i < 4; i++) {
int nx = jiho.x + dX[i];
int ny = jiho.y + dY[i];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
return jiho.time + 1;
}
if (map[nx][ny] == '.' && visited[nx][ny] == 0) {
visited[nx][ny] = 1;
jihos.offer(new Point(nx, ny, jiho.time + 1));
}
}
}
β
λΆλ³΄λ€ λ¨Όμ λμ°©νλ©΄ νμΆ μ±κ³΅!
β
λΆ(F
)κ³Ό μ§ν(J
)μ΄ κ°μ μκ°λμ νμ°λλ ꡬ쑰
π 6. κ²°λ‘
β
BFSλ₯Ό νμ©νμ¬ μ΅λ¨ μκ°μΌλ‘ νμΆ κ²½λ‘λ₯Ό μ°Ύμ
β
λΆ(F
)μ΄ λ¨Όμ νμ°λλλ‘ νμ¬, μ§ν(J
)μ΄ μ§λκ° κΈΈμ λ§μ
β
μ§ν(J
)μ΄ κ°μ₯μ리μ λλ¬νλ©΄ νμΆ μ±κ³΅!
**π‘ λ λμ λ°©λ²μ΄ μλ€λ©΄ λκΈ
λκΈλ¨κΈ°κΈ°