๐ฅ ๋ฐฑ์ค 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
)์ด ๊ฐ์ฅ์๋ฆฌ์ ๋๋ฌํ๋ฉด ํ์ถ ์ฑ๊ณต!
**๐ก ๋ ๋์ ๋ฐฉ๋ฒ์ด ์๋ค๋ฉด ๋๊ธ
๋๊ธ๋จ๊ธฐ๊ธฐ