๐ฅ ๋ฐฑ์ค 5472๋ฒ ๋ถ! (BFS ํ์ด ๋ฐ ์ค๋ฅ ๋ถ์)
๐ฅ ๋ฐฑ์ค 5472๋ฒ - ๋ถ! (BFS ํ์ด ๋ฐ ์ค๋ฅ ๋ถ์)
๐ 1. ๋ฌธ์ ์ค๋ช
์๊ทผ(@
)์ด๊ฐ ๋ถ(*
)์ด ๋ฒ์ง๋ ๊ฑด๋ฌผ์์ ํ์ถํ๋ ๋ฌธ์ ์
๋๋ค.
๋ถ(*
)์ ๋์์ ํผ์ง๊ณ , ์๊ทผ(@
)์ด๋ ํ ์นธ์ฉ ์ด๋ํ ์ ์์ต๋๋ค.
๋ฒฝ(#
)์ ์ด๋ํ ์ ์๊ณ , ์๊ทผ์ด๊ฐ ๊ฑด๋ฌผ์ ๊ฐ์ฅ์๋ฆฌ์ ๋๋ฌํ๋ฉด ํ์ถํ ์ ์์ต๋๋ค.
๐ 2. ์ ๋ ฅ ๋ฐ ์ถ๋ ฅ ์์
๐น ์ ๋ ฅ ์์
3
4 3
####
#*@#
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#*#.#*#
#.....#
####@##
๐น ์ถ๋ ฅ ์์
IMPOSSIBLE
5
IMPOSSIBLE
๐ ์ค๋ช
@
(์๊ทผ)๋ ์ด๋ํ๋ฉด์ ํ์ถ์ ์๋*
(๋ถ)์ ๋์์ ํ์ฐ๋๋ฉฐ ์๊ทผ์ ์ด๋์ ๋ฐฉํด- ํ์ถ์ด ๊ฐ๋ฅํ๋ฉด ์ต์ ์๊ฐ ์ถ๋ ฅ, ๋ถ๊ฐ๋ฅํ๋ฉด โIMPOSSIBLEโ ์ถ๋ ฅ
๐ 3. ํด๊ฒฐ ๋ฐฉ๋ฒ (BFS)
์ด ๋ฌธ์ ๋ ์ต๋จ ๊ฒฝ๋ก ํ์ ๋ฌธ์ ์ด๋ฏ๋ก,
BFS(๋๋น ์ฐ์ ํ์, Breadth-First Search)๋ฅผ ์ฌ์ฉํด์ผ ํฉ๋๋ค.
๐น ํต์ฌ ๋ก์ง
- ๋ถ(
*
)๊ณผ ์๊ทผ(@
)์ ๊ฐ๊ฐ BFS ํ์ ์ ์ฅ - ๋ถ(
*
)์ด ๋จผ์ ํ์ฐ, ๊ทธ ํ ์๊ทผ(@
)์ด ์ด๋ - ์๊ทผ(
@
)์ด ๊ฑด๋ฌผ์ ๊ฐ์ฅ์๋ฆฌ์ ๋๋ฌํ๋ฉด ์ฆ์ ํ์ถ - ์๊ทผ(
@
)์ด ์ด๋ํ ๊ณณ์ด ์์ผ๋ฉด โIMPOSSIBLEโ ์ถ๋ ฅ
๐ 4. ์ค๋ฅ ๋ถ์ ๋ฐ ํด๊ฒฐ
๐น ์ค๋ฅ 1: ์๋ชป๋ ๋ฐฐ์ด ๋ฒ์ ๊ฒ์ฌ
if (nx < 0 || ny < 0 || nx >= width || ny >= height) {
continue;
}
โ ๋ฌธ์ ์ :
nx
์ny
๋ ํ(row), ์ด(column)์ ๋ํ๋- ์ฌ๋ฐ๋ฅธ ๋ฒ์ ๊ฒ์ฌ๋
nx >= height
/ny >= width
๊ฐ ๋์ด์ผ ํจ
โ ํด๊ฒฐ ๋ฐฉ๋ฒ:
if (nx < 0 || ny < 0 || nx >= height || ny >= width) {
continue;
}
๐น ์ค๋ฅ 2: BFS์์ sangQ.poll()
์ ํ ๋ฒ๋ง ํธ์ถํ๋ ๋ฌธ์
Point sang = sangQ.poll();
โ ๋ฌธ์ ์ :
- ํ์ฌ ์ฝ๋์์๋
sangQ.poll()
์ด ํ ๋ฒ๋ง ํธ์ถ๋๋ฏ๋ก, ํ ๋ฒ์ BFS ๋ฃจํ์์ ์๊ทผ(@
)์ด ํ ์นธ์ฉ๋ง ์ด๋ํจ - ๋ฐ๋ฉด ๋ถ(
*
)์ ์ฌ๋ฌ ๊ฐ๊ฐ ๋์์ ํ์ฐํ๋ฏ๋ก, ์๊ทผ์ด๊ฐ ๋ถ์ ํผํ์ง ๋ชปํ๋ ๋ฌธ์ ๊ฐ ๋ฐ์
โ
ํด๊ฒฐ ๋ฐฉ๋ฒ:
๐ BFS์ โ๋ ๋ฒจ ๋จ์โ๋ก ์ด๋ํ๋๋ก sangSize
์ ์ฉ
int sangSize = sangQ.size();
for (int s = 0; s < sangSize; s++) {
Point sang = sangQ.poll();
// ์ด๋ ์ฒ๋ฆฌ
}
๐น ์ค๋ฅ 3: visited
์ขํ ์ฒด๊ณ ์ค๋ฅ
if (map[nextY][nextX] == '.' && visited[nextY][nextX] == 0) {
โ ๋ฌธ์ ์ :
- ๋ฐฐ์ด ์ขํ ์ฒด๊ณ(
map[nextY][nextX]
)์์nextX
์nextY
๊ฐ ๋ฐ๋๋ก ๋ค์ด๊ฐ map[y][x]
ํํ๋ก ์ ๊ทผํด์ผ ํจ
โ
ํด๊ฒฐ ๋ฐฉ๋ฒ:
๐ ์ฌ๋ฐ๋ฅธ ์ขํ ์ฒด๊ณ ์ ์ฉ
if (map[nextRow][nextCol] == '.' && visited[nextRow][nextCol] == 0) {
๐ 5. ์์ ๋ ์ฝ๋
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Back_5472 {
static class Point {
int x, y, time;
Point(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
}
static int[] dX = {0, 0, 1, -1}; // ์ด๋ ๋ฐฉํฅ (์ข์ฐ)
static int[] dY = {1, -1, 0, 0}; // ์ด๋ ๋ฐฉํฅ (์ํ)
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
int w = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
char[][] map = new char[h][w];
Queue<Point> fires = new LinkedList<>();
Queue<Point> sang = new LinkedList<>();
for (int j = 0; j < h; j++) {
String temp = br.readLine();
for (int k = 0; k < w; k++) {
map[j][k] = temp.charAt(k);
if (map[j][k] == '*') {
fires.offer(new Point(j, k, 0));
} else if (map[j][k] == '@') {
sang.offer(new Point(j, k, 0));
}
}
}
int result = bfs(w, h, map, sang, fires);
System.out.println(result == -1 ? "IMPOSSIBLE" : result);
}
}
private static int bfs(int width, int height, char[][] map, Queue<Point> sangQ, Queue<Point> fires) {
int[][] visited = new int[height][width];
while (!sangQ.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 >= height || ny >= width) {
continue;
}
if (map[nx][ny] == '.' || map[nx][ny] == '@') {
map[nx][ny] = '*';
fires.offer(new Point(nx, ny, fire.time + 1));
}
}
}
// ๐โโ๏ธ ์๊ทผ ์ด๋ (๋ ๋ฒจ BFS)
int sangSize = sangQ.size();
for (int s = 0; s < sangSize; s++) {
Point sang = sangQ.poll();
for (int i = 0; i < 4; i++) {
int nextRow = sang.x + dX[i];
int nextCol = sang.y + dY[i];
if (nextRow < 0 || nextCol < 0 || nextRow >= height || nextCol >= width) {
return sang.time + 1;
}
if (map[nextRow][nextCol] == '.' && visited[nextRow][nextCol] == 0) {
visited[nextRow][nextCol] = 1;
sangQ.offer(new Point(nextRow, nextCol, sang.time + 1));
}
}
}
}
return -1;
}
}
๐ก ๋ ๋์ ๋ฐฉ๋ฒ์ด ์๋ค๋ฉด ๋๊ธ๋ก ๊ณต์ ํด์ฃผ์ธ์! ๐
๋๊ธ๋จ๊ธฐ๊ธฐ