19237번: 어른 상어
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미
www.acmicpc.net
문제 확인
구현 문제입니다.
풀이
주어진 조건대로 풀면 쉽게 풀 수 있는 문제입니다.
일일이 모든 냄새의 수명을 -1씩 하면 느리므로 냄새를 뿌리면 해당 냄새의 수명을 depth + k로 기록하여 depth가 이를 넘을 경우 접근할 수 있도록 합니다.
상어를 1부터 m까지 오름차순으로 이동하여 겹치는 상어는 그 순간 내보낼 수 있도록 합니다.
주의해야 할 점은 냄새와 상어의 위치를 구분지어야 같은 칸에 상어가 들어갈 수 있는 여지가 생기므로 따로 변수를 두어 관리합니다.
코드
|
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
|
#include <cstdio>
#include <cstring>
typedef struct shark {
int x, y, d;
int priority[4][4];
}shark;
typedef struct node {
int num, sk, cnt;
};
int main() {
int n, m, k;
shark sk[401];
node map[20][20];
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
scanf("%d", &map[i][j].num);
if (map[i][j].num) {
map[i][j].sk = map[i][j].num;
map[i][j].cnt = k;
sk[map[i][j].num] = { i, j };
}
}
for (int i = 1; i <= m; i++)
scanf("%d", &sk[i].d), sk[i].d--;
for (int i = 1; i <= m; i++)
for (int j = 0; j < 4; j++)
for (int k = 0; k < 4; k++) {
scanf("%d", &sk[i].priority[j][k]);
--sk[i].priority[j][k];
}
int dx[4] = { -1,1,0,0 },
dy[4] = { 0,0,-1,1 };
int depth = 0, cnt = m - 1;
while (depth < 1000) {
depth++;
for (int i = 1; i <= m; i++) {
if (sk[i].x == -1) continue;
map[sk[i].x][sk[i].y].num = 0;
bool t = true;
for (int d = 0; t && d < 4; d++) {//빈칸
int nd = sk[i].priority[sk[i].d][d];
int nx = sk[i].x + dx[nd], ny = sk[i].y + dy[nd];
if (nx < 0 || ny < 0 || nx == n || ny == n || map[nx][ny].cnt >= depth) continue;
t = false;
if (map[nx][ny].num) {//오름차순으로 검색하므로 겹치면 내보냄
sk[i].x = -1;
cnt--;
}
else {
sk[i].x = nx;
sk[i].y = ny;
sk[i].d = nd;
map[nx][ny].num = i;
map[nx][ny].sk = i;
}
}
if (t) {//냄새
for (int d = 0; d < 4; d++) {
int nd = sk[i].priority[sk[i].d][d];
int nx = sk[i].x + dx[nd], ny = sk[i].y + dy[nd];
if (nx < 0 || ny < 0 || nx == n || ny == n || map[nx][ny].sk != i) continue;
sk[i].x = nx;
sk[i].y = ny;
sk[i].d = nd;
break;
}
}
}
for (int i = 1; i <= m; i++) {//냄새 뿌림
if (sk[i].x == -1) continue;
map[sk[i].x][sk[i].y].cnt = depth + k;
}
if (!cnt) {
printf("%d", depth);
return 0;
}
}
printf("-1");
}
|
cs |
반응형
'알고리즘 문제 > [백준]' 카테고리의 다른 글
| [백준] 17833 원판 돌리기 (0) | 2021.03.30 |
|---|---|
| [백준] 16719 ZOAC (0) | 2021.03.30 |
| [백준] 9370 미확인 도착지 (0) | 2021.03.16 |
| [백준] 9660 돌 게임 6 (0) | 2021.03.15 |
| [백준] 2493 탑 (0) | 2021.03.15 |