algorithm/bfs
boj 14923 미로 탈출
와이에쓰
2021. 3. 29. 21:33
14923번: 미로 탈출
홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이
www.acmicpc.net
(hx, hy)에서 출발하여 (ex, ey)까지 갈 수 있는 최단거리를 출력합니다.
맵에는 벽이 있으며 벽을 1개까지 부술 수 있습니다.
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
이 문제와 같은 풀이방식입니다.
이 문제와 다른점은 출발점과 도착점이 고정이 아니라는 점입니다.
visit[x][y][cnt] : (x, y)에 벽을 부수고 방문한 경우와 안부수고 방문한 경우를 나눠줍니다.
탈출이 가능하면 거리를 출력, 불가능하면 -1을 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Deque<int[]> dq = new ArrayDeque<>();
static int list[][] = new int[1001][1001];
static boolean visit[][][] = new boolean[1001][1001][2];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int N, M, ex, ey;
static void bfs() {
for (int t = 1;; t++) {
int size = dq.size();
while (size-- > 0) {
int x = dq.peek()[0];
int y = dq.peek()[1];
int cnt = dq.poll()[2];
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 1 || ny < 1 || nx > N || ny > M)
continue;
if (list[nx][ny] == 1) {
if (cnt > 0 || visit[nx][ny][1])
continue;
dq.add(new int[] { nx, ny, 1 });
visit[nx][ny][1] = true;
} else {
if (visit[nx][ny][cnt])
continue;
dq.add(new int[] { nx, ny, cnt });
visit[nx][ny][cnt] = true;
if (nx == ex && ny == ey) {
System.out.println(t);
return;
}
}
}
}
if (dq.isEmpty()) {
System.out.println(-1);
return;
}
}
}
static void input() throws Exception {
int x, y;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
dq.add(new int[] { x, y, 0 });
visit[x][y][0] = true;
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
ex = x;
ey = y;
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
input();
bfs();
}
}
|
cs |