1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
bfs 탐색인데 4방탐색에 위 사진과 같은 이동방식이 추가되었습니다.
위 사진처럼 말과 같이 움직일 수 있는 횟수가 K로 정해져있습니다. (0 <= K <= 30)
그러므로 방문체크는 3차원 배열로 해줍니다.
visit[x][y][k] : 말과 같이 움직인 횟수가 k번인 상태로 (x, y)에 도착한 경우
저는 방향탐색에 대한 좌표이동을 인덱스를 기준으로 나누었습니다.
1. 0 ~ 3번 인덱스 : 4방탐색
2. 4 ~ 11번 인덱스 : 말처럼 이동
4방탐색의 경우 k의 변화 없이 이동시켜줍니다.
말처럼 이동하는 경우 K미만으로 움직였을 경우에만 움직여줍니다.
(N - 1, M - 1)에 도달하였으면 시간을 출력합니다.
[C++]
|
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
|
#include <iostream>
#include <queue>
using namespace std;
queue<pair<pair<int, int>, pair<int, int> > > q;
bool visit[200][200][31];
int map[200][200];
int x_direct[] = { 0,1,0,-1,-2,-1,1,2,2,1,-1,-2 }, y_direct[] = { 1,0,-1,0,1,2,2,1,-1,-2,-2,-1 };
int K, H, W, ans = -1;
void bfs() {
while (!q.empty()) {
int x = q.front().first.first;
int y = q.front().first.second;
int cnt = q.front().second.first;
int horse = q.front().second.second;
q.pop();
if (x == H - 1 && y == W - 1) {
ans = cnt;
return;
}
for (int i = 0; i < 12; i++) {
int xx = x + x_direct[i];
int yy = y + y_direct[i];
if (xx < 0 || yy < 0 || xx >= H || yy >= W) continue;
if (map[xx][yy] == 1) continue;
if (x_direct[i] == 2 || x_direct[i] == -2 || y_direct[i] == 2 || y_direct[i] == -2) {
if (visit[xx][yy][horse + 1] || horse == K) continue;
q.push(make_pair(make_pair(xx, yy), make_pair(cnt + 1, horse + 1)));
visit[xx][yy][horse + 1] = true;
}
else {
if (visit[xx][yy][horse]) continue;
q.push(make_pair(make_pair(xx, yy), make_pair(cnt + 1, horse)));
visit[xx][yy][horse] = true;
}
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> K >> W >> H;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> map[i][j];
}
}
q.push(make_pair(make_pair(0, 0), make_pair(0, 0)));
visit[0][0][0] = true;
bfs();
cout << ans << '\n';
return 0;
}
|
cs |
[Java]
|
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
|
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 int list[][] = new int[201][201];
static boolean visit[][][] = new boolean[201][201][31];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 },
{ 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 } };
static int N, M, K;
static void bfs() {
Deque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] { 0, 0, 0 });
visit[0][0][0] = true;
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];
if (x == N - 1 && y == M - 1) {
System.out.println(t - 1);
return;
}
for (int i = 0; i < 12; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (list[nx][ny] == 1)
continue;
if (i < 4) {
if (visit[nx][ny][cnt])
continue;
dq.add(new int[] { nx, ny, cnt });
visit[nx][ny][cnt] = true;
} else {
if (cnt + 1 > K || visit[nx][ny][cnt + 1])
continue;
dq.add(new int[] { nx, ny, cnt + 1 });
visit[nx][ny][cnt + 1] = true;
}
}
}
if (dq.isEmpty()) {
System.out.println(-1);
return;
}
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
input();
bfs();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 17836 공주님을 구해라! (0) | 2021.03.26 |
|---|---|
| boj 9205 맥주 마시면서 걸어가기 (0) | 2021.03.25 |
| boj 2589 보물섬 (0) | 2021.03.16 |
| boj 11559 Puyo Puyo (0) | 2021.02.26 |
| boj 15653 구슬 탈출 4 (0) | 2021.02.22 |