알고리즘/백준 BAEK JOON
16236.아기상어
IMyoungho
2020. 5. 31. 15:06
이번에 풀어볼 문제는 백준 16236의 아기상어이다. 시뮬레이션 + 탐색의 문제이며 요즘 점점 설계의 중요성을 깨닫는다.
이 문제를 잘 풀기 위해서는 자신이 구하고자하는 내용들의 순서로직의 설계를 잘해주어야 한다.
아직 설계능력이 많이 미숙한 것 같다. 하다보면 늘겠지..
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가��
www.acmicpc.net
< Code 설명 >
|
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
|
#pragma warning(disable:4996) #include <iostream>
#include <queue>
#include <string.h>
#define MAX 21
#define BOOL_CMP 777 //비교대상의 될 임의의 값
using namespace std;
int map[MAX][MAX]; // 맵이 저장되는 공간
int check[MAX][MAX]; // 걸린 시간이 저장되는 공간
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int n, src_x, src_y, tmp_x, tmp_y, help_cmp;
int shark = 2; // 상어의 크기
queue <pair<int, int>>spot; // 좌표저장될 큐
void showme(){ // 현재 배열내용 보여주기
cout << "\n";
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cout << map[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
cout << "\n";
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cout << check[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
}
void reset(){ // 초기화
help_cmp =tmp_x = tmp_y = BOOL_CMP;// 비교대상과 임시좌표 초기화
memset(check, 0, sizeof(check)); // check 배열 초기화
}
void queue_clear(){ // 큐 초기화
int size = spot.size();
for (int i = 0; i < size; i++)
spot.pop();
}
void search(int x, int y){ //탐색(BFS)
while (!spot.empty()){
x = spot.front().first; x좌표 사용
y = spot.front().second; y좌표 사용
spot.pop(); // 사용했으니 버린다
//showme();
for (int i = 0; i < 4; i++){
int ax = x + dx[i]; // 좌표기준 상하좌우 탐색
int ay = y + dy[i]; // 좌표기준 상하좌우 탐색
if (ax < 0 || ay < 0 || ax >= n || ay >= n)
continue; // 맵 범위를 벗어나면 넘어감
// 먹을수도 있고 지나갈 수도 있는 경우
if (!check[ax][ay] && map[ax][ay] <= shark){
// 이동 했으므로 시간 증가
check[ax][ay] = check[x][y] + 1;
spot.push(make_pair(ax, ay));//해당 좌표 저장
// 먹을 수 있는 먹이가 있다면
if (map[ax][ay]!= 0 && map[ax][ay] < shark){
// 먹을 수 있는 첫 번째 먹이체크
if (help_cmp > check[ax][ay]){
// 해당 크기 기록해놓음
help_cmp = check[ax][ay];
tmp_x = ax; // 해당 x좌표 기록
tmp_y = ay; // 해당 y좌표 기록
}
// 먹을 수 있는 먹이가 여러개인 경우
else if (help_cmp == check[ax][ay]){
// x축의 크기가 같다면 위쪽이 먼저
if (tmp_x == ax){
// y값이 작을 수록 위쪽이므로
if (tmp_y > ay)
//작은값 저장
tmp_y = ay;
}
// x축은 왼쪽이 우선이다.
else if (tmp_x > ax){
tmp_x = ax;
tmp_y = ay;
}
}
}
}
}
}
}
int main() {
//freopen("16236.txt", "r", stdin);
cin >> n;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> map[i][j];
if (map[i][j] == 9){
spot.push(make_pair(i, j));
map[i][j] = 0; //큐에 넣었으니 0으로 초기화
}
}
}
int ans = 0; // 총 걸린시간
int cnt = 0; // 먹은 먹이량
while (true){
reset(); // 초기화
src_x = spot.front().first; // 시작 x좌표 사용
src_y = spot.front().second;// 시작 y좌표 사용
search(src_x, src_y); // 탐색시작
// 임의의 비교값이 변경되었다면 탐색내의 로직상 먹이를 발견했다는 의미
if (tmp_x != BOOL_CMP && tmp_y != BOOL_CMP){
cnt += 1; // 먹은 먹이수 +1
ans += check[tmp_x][tmp_y]; // 해당 시간값 누산
map[tmp_x][tmp_y] = 0; // 먹은 물고기 0으로 초기화
if (cnt == shark){// 상어크기만큼 먹었다면
shark += 1; // 상어크기 +1
cnt = 0; // 다시 카운트해야하므로 0
}
queue_clear(); // 큐를 비워주고
//먹은 부분부터 시작하기위해 좌표저장
spot.push(make_pair(tmp_x, tmp_y));
}
else // 먹을게 없다면 종료
break;
}
cout << ans << "\n";
return 0;
}
|
cs |
반응형