๐งฑ ๋ฐฑ์ค 2206๋ฒ ๋ฒฝ ๋ถ์๊ณ ์ด๋ํ๊ธฐ (BFS ํ์ด)
๐งฑ ๋ฐฑ์ค 2206๋ฒ - ๋ฒฝ ๋ถ์๊ณ ์ด๋ํ๊ธฐ (BFS ํ์ด)
๐ 1. ๋ฌธ์ ์ค๋ช
NรM ํฌ๊ธฐ์ ๋ฐฐ์ด์ด ์ฃผ์ด์ง๊ณ ,
๋ฒฝ(1
)์ด ์๋ ๊ฒฝ์ฐ ํ ๊ฐ์ ๋ฒฝ์ ๋ถ์๊ณ ์ง๋๊ฐ ์ ์๋ค.
์ต๋จ ๊ฑฐ๋ฆฌ๋ก ๋์ฐฉ์ (N-1, M-1)
๊น์ง ์ด๋ํด์ผ ํ๋ค.
๐ 2. ์ ๋ ฅ ๋ฐ ์ถ๋ ฅ ์์
๐น ์ ๋ ฅ ์์
6 4
0100
1110
1000
0000
0111
0000
๐น ์ถ๋ ฅ ์์
15
๐ ์ค๋ช
(0,0)
์์(5,3)
๊น์ง ์ต๋จ ๊ฑฐ๋ฆฌ๋ก ์ด๋- ๋ฒฝ์ ํ ๋ฒ ๋ถ์๋ ๊ฒฝ์ฐ ๋ ๋น ๋ฅธ ๊ฒฝ๋ก ๊ฐ๋ฅ
๐ 3. ํด๊ฒฐ ๋ฐฉ๋ฒ (BFS)
์ด ๋ฌธ์ ๋ ์ต๋จ ๊ฒฝ๋ก ๋ฌธ์ ์ด๋ฏ๋ก
BFS(๋๋น ์ฐ์ ํ์, Breadth-First Search)๋ฅผ ์ฌ์ฉํด์ผ ํ๋ค.
๐น BFS๋ฅผ ์ฌ์ฉํด์ผ ํ๋ ์ด์
- ๋ชจ๋ ์นธ์ ํ ๋ฒ์ฉ ๋ฐฉ๋ฌธํ๋ ๊ฒฝ์ฐ O(NรM)
- DFS(๊น์ด ์ฐ์ ํ์)๋ณด๋ค BFS๊ฐ ์ต๋จ ๊ฑฐ๋ฆฌ ํ์์ ์ ํฉ
- BFS๋ฅผ ํ์ฉํ์ฌ ๋ฒฝ์ ํ ๋ฒ๋ง ๋ถ์ ์ ์๋๋ก ๊ด๋ฆฌ
๐ 4. ํต์ฌ ์ฝ๋ ๋ถ์
static class Point {
int x, y, count;
boolean destroyed; // ๋ฒฝ์ ๋ถ์๋์ง ์ฌ๋ถ
public Point(int x, int y, int count, boolean destroyed) {
this.x = x;
this.y = y;
this.count = count;
this.destroyed = destroyed;
}
}
โ
Point
ํด๋์ค
x
,y
โ ํ์ฌ ์ขํcount
โ ์ด๋ ๊ฑฐ๋ฆฌ (์ต๋จ ๊ฑฐ๋ฆฌ)destroyed
โ ๋ฒฝ์ ๋ถ์๋์ง ์ฌ๋ถ (true
= ๋ถ์จ)
๐น visited
3์ฐจ์ ๋ฐฐ์ด (๋ฒฝ์ ๋ถ์ ๊ฒฝ์ฐ vs ๋ถ์์ง ์์ ๊ฒฝ์ฐ)
boolean[][][] visited = new boolean[N][M][2];
โ
visited[N][M][0]
โ ๋ฒฝ์ ๋ถ์์ง ์๊ณ ๋ฐฉ๋ฌธํ ๊ฒฝ์ฐ
โ
visited[N][M][1]
โ ๋ฒฝ์ ๋ถ์ ํ ๋ฐฉ๋ฌธํ ๊ฒฝ์ฐ
โ
๊ฐ์ ์์น๋ฅผ ๋ฒฝ์ ๋ถ์ ์ํ/๋ถ์์ง ์์ ์ํ๋ก ๋ฐฉ๋ฌธํ ์ ์์ผ๋ฏ๋ก 3์ฐจ์ ๋ฐฐ์ด์ ์ฌ์ฉ
๐น BFS ํ์ ๊ณผ์
Queue<Point> points = new LinkedList<>();
points.offer(new Point(0, 0, 1, false));
visited[0][0][0] = true;
โ BFS๋ฅผ ์ํ ํ ์ด๊ธฐํ
(0,0)
์์ ์์ (count=1
)- ์ฒ์์๋ ๋ฒฝ์ ๋ถ์์ง ์์ ์ํ (
destroyed=false
)
๐น BFS ํ์ (๋ฒฝ ๋ถ์๊ธฐ ๋ก์ง ํฌํจ)
for (int i = 0; i < 4; i++) {
int dirX = now.x + dX[i];
int dirY = now.y + dY[i];
if (dirX >= N || dirX < 0 || dirY >= M || dirY < 0) continue;
// ์ด๋ ๊ฐ๋ฅ (๋น ๊ณต๊ฐ)
if (map[dirX][dirY] == '0') {
if (!now.destroyed && !visited[dirX][dirY][0]) {
points.offer(new Point(dirX, dirY, now.count + 1, false));
visited[dirX][dirY][0] = true;
} else if (now.destroyed && !visited[dirX][dirY][1]) {
points.offer(new Point(dirX, dirY, now.count + 1, true));
visited[dirX][dirY][1] = true;
}
}
// ๋ฒฝ ๋ถ์๊ธฐ (๋ฒฝ์ ํ ๋ฒ๋ ๋ถ์์ง ์์ ๊ฒฝ์ฐ)
else if (map[dirX][dirY] == '1') {
if (!now.destroyed) {
points.offer(new Point(dirX, dirY, now.count + 1, true));
visited[dirX][dirY][1] = true;
}
}
}
โ ์ด๋ํ ์ ์๋ ๊ฒฝ์ฐ
- ๋น ๊ณต๊ฐ(
0
)์ผ ๋ โ ๋ฒฝ์ ๋ถ์ ์ฌ๋ถ์ ๋ฐ๋ผ ๋ฐฉ๋ฌธ ์ฒดํฌ - ๋ฒฝ(
1
)์ ๋ถ์ ์ ์๋ ๊ฒฝ์ฐ โ ํ ๋ฒ๋ง ๋ถ์๋๋ก ์ค์
๐น ๋ชฉํ ์ง์ ๋์ฐฉ ์ฌ๋ถ ํ์ธ
if (now.x == N - 1 && now.y == M - 1) {
return now.count;
}
โ
๋์ฐฉํ๋ฉด ์ฆ์ ์ต๋จ ๊ฑฐ๋ฆฌ ๋ฐํ
โ
BFS๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๋ณด์ฅํ๋ฏ๋ก, ์ฒซ ๋ฒ์งธ ๋์ฐฉํ ๊ฒฝ๋ก๊ฐ ํญ์ ์ต๋จ ๊ฑฐ๋ฆฌ
๐ 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_2206 {
static class Point {
int x, y, count;
boolean destroyed;
public Point(int x, int y, int count, boolean destroyed) {
this.x = x;
this.y = y;
this.count = count;
this.destroyed = destroyed;
}
}
static int[] dX = {0, 0, 1, -1};
static int[] dY = {1, -1, 0, 0};
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
char[][] map = new char[N][M];
for (int i = 0; i < N; i++) {
String temp = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = temp.charAt(j);
}
}
System.out.println(bfs(map));
}
private static int bfs(char[][] map) {
Queue<Point> points = new LinkedList<>();
points.offer(new Point(0, 0, 1, false));
boolean[][][] visited = new boolean[N][M][2];
visited[0][0][0] = true;
while (!points.isEmpty()) {
Point now = points.poll();
if (now.x == N - 1 && now.y == M - 1) {
return now.count;
}
for (int i = 0; i < 4; i++) {
int dirX = now.x + dX[i];
int dirY = now.y + dY[i];
if (dirX >= N || dirX < 0 || dirY >= M || dirY < 0) continue;
if (map[dirX][dirY] == '0') {
if (!now.destroyed && !visited[dirX][dirY][0]) {
points.offer(new Point(dirX, dirY, now.count + 1, false));
visited[dirX][dirY][0] = true;
} else if (now.destroyed && !visited[dirX][dirY][1]) {
points.offer(new Point(dirX, dirY, now.count + 1, true));
visited[dirX][dirY][1] = true;
}
} else if (map[dirX][dirY] == '1') {
if (!now.destroyed) {
points.offer(new Point(dirX, dirY, now.count + 1, true));
visited[dirX][dirY][1] = true;
}
}
}
}
return -1;
}
}
๋๊ธ๋จ๊ธฐ๊ธฐ