문제링크 : https://www.acmicpc.net/problem/16236
문제를 읽고나면 문제의 조건이 매우 까다롭다는 걸
우리 모두 공감 할 수 있다.
자신이 먹을 수 있는 물고기의 개수를 새면서
BFS를 이용해 가까운 먹이를 찾고
가까운 먹이가 여러개일경우 위쪽에 있는 지 같은 래밸이라면 왼쪽에 있는지 확인해주면 된다.
그래서 이번에 내가 고민한점은 다음과 같다.
① bfs를 이용한 서치
② 답이 여러개일 경우 우선순위에 맞게 처리
③ 상어 객채 처리
1. bfs
bfs를 이용하여 탐색을 할때 중요한점은 지난 점을 다시 지나지 않는 것이였다. 이를 위해 바다속과 똑같은 크기의
배열을 만들어 search할 때 마다 들린곳은 처리 해주었으며 먹이를 먹은 경우 그 곳에서부터 다시 bfs를 시작하게 만들었다.
2. 답이 여러개인 경우
답이 여러개인 경우를 위해 답을 찾은경우 별도의 queue에 저장하여 queue의 사이즈가 0보다 큰경우 우선순위에 해당하는 점을 찾아
그곳으로 상어를 이동시켰다.
3. 상어 처리
상어는 한개의 struct로 만들어 한번에 정보를 담았다. 좌표, 상어의 크기, 먹은 물고기 개수를 저장했다.
그렇게 작성한 코드는 다음과 같다.
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;
queue<P> movePoint;
queue<P> answerPoint;
int map[21][21] = { 0 };
int mapSize = 0;
int fish[7] = { 0 };
int answer = 0;
int nowLevel = 1;
int dx[4] = { 0,-1,1,0 };
int dy[4] = { -1,0,0,1 };
bool checkmap[21][21] = { true };
struct Shark {
int size = 2;
int eat = 0;
int x;
int y;
};
Shark babaShark;
void setting(int tmp, int y, int x) {
if (tmp == 9) {
map[y][x] = 0;
babaShark.x = x;
babaShark.y = y;
movePoint.push({ babaShark.y,babaShark.x });
}
else if (tmp == 1) {
fish[1]++;
}
else if (tmp == 2) {
fish[2]++;
}
else if (tmp == 3) {
fish[3]++;
}
else if (tmp == 4) {
fish[4]++;
}
else if (tmp == 5) {
fish[5]++;
}
else if (tmp == 6) {
fish[6]++;
}
}
void input() {
cin >> mapSize;
for (int i = 0; i< mapSize; i++) {
for (int j = 0; j<mapSize; j++) {
int tmp;
cin >> tmp;
map[i][j] = tmp;
setting(tmp, i, j);
}
}
}
void clearQueue() {
while (movePoint.size()>0) {
movePoint.pop();
}
}
void answerCheck() {
int x = mapSize;
int y = mapSize;
while (answerPoint.size() > 0) {
P tmp = answerPoint.front();
answerPoint.pop();
if (tmp.first < y) {
y = tmp.first;
x = tmp.second;
}
else if (tmp.first == y) {
if (tmp.second < x) {
y = tmp.first;
x = tmp.second;
}
}
}
map[y][x] = 0;
fish[nowLevel]--;
clearQueue();
movePoint.push({ y,x });
babaShark.eat++;
if (babaShark.eat == babaShark.size) {
babaShark.size++;
babaShark.eat = 0;
}
}
void check(int y, int x) {
if (map[y][x]<babaShark.size & map[y][x] != 0) {
answerPoint.push({ y,x });
}
else if (map[y][x] == babaShark.size || map[y][x] == 0) {
movePoint.push({ y,x });
}
}
int findOne() {
bool find = true;
int count = 0;
int size = movePoint.size();
while (find & size>0) {
count++;
for (int k = 0; k < size; k++) {
P tmp = movePoint.front();
movePoint.pop();
if (checkmap[tmp.first][tmp.second]) {
checkmap[tmp.first][tmp.second] = false;
for (int i = 0; i < 4; i++) {
if (tmp.first + dy[i] >= 0 & tmp.second + dx[i] >= 0 & tmp.first + dy[i]<mapSize & tmp.second + dx[i]<mapSize) {
check(tmp.first + dy[i], tmp.second + dx[i]);
}
}
}
}
if (answerPoint.size()>0) {
answerCheck();
return count;
}
size = movePoint.size();
}
return 0;
}
void refreshCheckMap() {
for (int i = 0; i<mapSize; i++) {
for (int j = 0; j<mapSize; j++) {
checkmap[i][j] = true;
}
}
}
/*
void print() {
for (int i = 0; i < mapSize; i++) {
for (int j = 0; j < mapSize; j++) {
cout << map[i][j];
}
cout << endl;
}
cout << endl;
}
*/
void levelfind() {
while (fish[nowLevel]>0 & movePoint.size()>0) {
refreshCheckMap();
answer = answer + findOne();
//print();
}
nowLevel++;
}
int main() {
input();
while (nowLevel < babaShark.size) {
levelfind();
}
cout << answer;
}
'알고리즘' 카테고리의 다른 글
| [C++] 백준 BOJ 3023 마술사 이민혁 (0) | 2019.01.12 |
|---|---|
| [C++] 백준 BOJ 7569 토마토 (0) | 2019.01.10 |
| [C++] 백준 BOJ 10815 숫자카드 (0) | 2019.01.09 |