전체/알고리즘 문제풀이
백준 16236. 아기 상어
승케이
2019. 4. 12. 17:44
문제출처 : baekjoon online judge
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크
www.acmicpc.net
문제의 큰 틀은 bfs를 활용하는 방법으로 접근했습니다.
bfs로 탐색하다 그 거리에 다음 후보지가 있으면 그 후보지는 que에 넣지 않고 다음 거리 탐색하기 전에 그곳을 기점ㅇ으로 다시 bfs를 실행합니다.
만약 같은 거리에 후보지가 많으면 y, x 값을 비교해 최종 후보지를 선택합니다.
|
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
|
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int map[22][22];
int check[22][22];
int que_x[400];
int que_y[400];
int que_d[400];
int rear = 0;
int top = 0;
int fx, fy;
int now = 2; //
int sum = 0; // 먹은 물고기 개수
int dir_x[4] = { 0,-1,0,1 };
int dir_y[4] = { -1,0,1,0 };
int dist = 0;
void bfs() {
int checking = 0;
while (rear < top) {
int x = que_x[rear];
int y = que_y[rear];
int d = que_d[rear++];
if (que_d[top - 1] == d) { // 다음 거리를 탐색할 때, 이전에 이동할 수 있는 곳이 있나 확인한 후 그곳으로 이동해서 다시 bfs
if (checking == 1) { //갈 곳이 있는지 체크
map[fy][fx] = 0;
sum = (sum + 1) % now;
if (sum == 0)
now++; //여기까지 먹었을 때 처리
top = 0;
rear = 0;
memset(check, 0, sizeof(check));
check[fy][fx] = 1;
que_x[top] = fx;
que_y[top] = fy;
que_d[top++] = 0; // 초기화
bfs(); // 다시 bfs
return;
}
}
for (int i = 0; i < 4; i++) {
int next_x = x + dir_x[i];
int next_y = y + dir_y[i];
int next_d = d + 1;
if (map[next_y][next_x] < now && map[next_y][next_x] > 0) { // 후보지일 때, 큐에 넣지 않고 이전 후보지와 비교
if (checking == 0) { //
fx = next_x;
fy = next_y;
dist += next_d;
}
else {
if (next_y < fy) { // 더 위에있는 후보지 선택
fy = next_y;
fx = next_x;
}
else if(next_y == fy){
if (next_x < fx) { //더 왼쪽에 있는 후보지 선택
fy = next_y;
fx = next_x;
}
}
}
que_d[top++] = next_d;
checking = 1;
}
if (checking == 0) {
if (map[next_y][next_x] == 0 || map[next_y][next_x] == now) {
if (check[next_y][next_x] == 0) {
check[next_y][next_x] = 1;
que_x[top] = next_x;
que_y[top] = next_y;
que_d[top++] = next_d;
}
}
}
}
}
}
int main() {
memset(map, -1, sizeof(map));
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> map[i][j];
if (map[i][j] == 9) {
fx = j;
fy = i;
}
}
}
map[fy][fx] = 0;
check[fy][fx] = 1;
que_x[top] = fx;
que_y[top++] = fy;
bfs();
cout << dist << endl;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
|
|
의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!