https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 자연수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.
www.acmicpc.net
최소 동작수를 구하는 문제이므로 bfs로 이동할 수 있는 방법을 매번 사용하여 정답을 구하면 된다.
벽 부수고 이동하기 문제와 비슷하게 풀었다.
인접한 네 방향으로 이동하는 경우와 아직 능력을 k번만큼 사용하지 않았다면 말의 움직임처럼 이동하는 경우를 모두 큐에 넣어주고 이동할 때마다 배열에 동작 수를 저장한다.
이때 해당칸에 도착할 때 능력을 몇 번 사용했는지에 따라 다르므로 삼차원 배열을 사용한다.
visit[x][y][z] = (x, y) 좌표에 능력을 z번 사용해서 온 동작의 수
마지막 visit[h-1][w-1][0]부터 visit[h-1][w-1][k]까지 중 최솟값이 정답이다.
(마지막 칸에 도착했을때 능력을 0번 사용한 경우부터 k번 사용한 경우 중 최솟값)
|
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int k, w, h;
int map[200][200];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int hx[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
int hy[] = { -1, 1, -2, 2, -2, 2, -1, 1 };
int visit[200][200][31];
struct Pos {
int x;
int y;
int cnt; //능력을 사용한 횟수
Pos(int a, int b, int c) {
x = a;
y = b;
cnt = c;
}
};
void bfs(int x, int y) {
memset(visit, -1, sizeof(visit));
queue<Pos> q;
q.push(Pos(x, y, 0));
visit[x][y][0] = 0;
int cnt, nx, ny;
while (!q.empty()) {
x = q.front().x;
y = q.front().y;
cnt = q.front().cnt;
q.pop();
//능력을 아직 사용할 수 있어서 말처럼 움직이는 경우
if (cnt < k) {
for (int i = 0; i<8; i++) {
nx = x + hx[i];
ny = y + hy[i];
//범위 체크
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
//장애물 확인
if (map[nx][ny] == 1) continue;
//방문확인
if (visit[nx][ny][cnt + 1] != -1) continue;
//능력을 사용하였으므로 cnt를 증가시킨 채로 큐에 넣는다.
q.push(Pos(nx, ny, cnt + 1));
visit[nx][ny][cnt + 1] = visit[x][y][cnt] + 1;
}
}
//인접한 칸으로 이동하는 경우
for (int i = 0; i<4; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
if (map[nx][ny] == 1) continue;
if (visit[nx][ny][cnt] != -1) continue;
//능력을 사용하지 않은 경우이므로 cnt는 그대로이다
q.push(Pos(nx, ny, cnt));
visit[nx][ny][cnt] = visit[x][y][cnt] + 1;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> k;
cin >> w >> h;
for (int i = 0; i<h; i++) {
for (int j = 0; j<w; j++) {
cin >> map[i][j];
}
}
bfs(0, 0);
int ans = 2100000000;
for (int i = 0; i <= k; i++) {
if (visit[h - 1][w - 1][i] != -1 && ans > visit[h - 1][w - 1][i]) {
ans = visit[h - 1][w - 1][i];
}
}
if (ans == 2100000000) cout << -1 << '\n';
else cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 17780. 새로운 게임 (0) | 2020.02.03 |
|---|---|
| [BOJ] 17837. 새로운 게임 2 (0) | 2020.02.03 |
| [BOJ] 2532. 반도체 설계 (0) | 2020.01.29 |
| [BOJ] 12783. 가장 긴 증가하는 부분 수열 3 (0) | 2020.01.29 |
| [BOJ] 12015. 가장 긴 증가하는 부분 수열 2 (0) | 2020.01.29 |