아기 상어
https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
가장 처음에 아기 상어의 크기는 2
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.
상어 구조체를 만들어주면 되겠다.
if 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
else 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때,
지나야하는 칸의 개수의 최솟값이다.
이걸 bfs로 해야할 거 같다.
최단 경로니까
최단 경로는 어떻게 구하는가? nagasa 배열
미로 탐색 문제를 떠올리면 된다.
bfs 할 때 이 조건 생각하면서 해준다.
크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
마지막으로 못 갈 수도 있는 경우를 생각해야하므로
bfs의 return 값은 vector<f_info>로 한다.
vector의 크기가 0이면 못 간거니까 while문 탈출
항상 visited 배열 같은 것은
memset으로 초기화 해주는 것을 까먹지 말자
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면,
가장 왼쪽에 있는 물고기를 먹는다
시간 -> 행 -> 열 순으로 sort 하면 되겠다.
이제 이걸 코드로 나타내자.
|
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int map[25][25];
int nagasa[25][25];
bool visited[25][25];
int n;
struct s_info {
int bulk;
int kosu;
int row;
int col;
};
struct f_info
{
int sigan;
int kugi;
int hang;
int yul;
};
struct s_info shark;
vector<f_info> fish;
// 맵 전체를 순회하면서
// 상어 크기보다 작으면 vector에 넣는다
vector<f_info> bfs()
{
queue<pair<int, int>> q;
q.push({ shark.row, shark.col });
visited[shark.row][shark.col] = true;
vector<f_info> tmp;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n)
{
if (!visited[nx][ny] && map[nx][ny] <= shark.bulk)
{
nagasa[nx][ny] = nagasa[x][y] + 1;
visited[nx][ny] = true;
q.push({ nx, ny });
if (map[nx][ny] != 0 && map[nx][ny] < shark.bulk)
{
tmp.push_back({ nagasa[nx][ny], map[nx][ny], nx, ny });
}
}
}
}
}
return tmp;
}
bool operator < (const f_info& A, const f_info& B)
{
if (A.sigan == B.sigan)
{
if (A.hang == B.hang)
return A.yul < B.yul;
else
return A.hang < B.hang;
}
return A.sigan < B.sigan;
}
void evolve()
{
// 진화 가능한지 체크
if (shark.bulk == shark.kosu)
{
shark.bulk++;
shark.kosu = 0;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
shark.bulk = 2;
shark.kosu = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> map[i][j];
if (map[i][j] == 9)
{
shark.row = i;
shark.col = j;
map[i][j] = 0;
}
}
}
int ans = 0;
while (true)
{
int fish_cnt = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (map[i][j] != 0)
{
if (map[i][j] < shark.bulk)
{
// 먹을 수 있는 물고기 개수를 센다
fish_cnt++;
}
}
}
}
memset(nagasa, 0, sizeof(nagasa));
// 먹을 수 있는 물고기가 없다
if (fish_cnt == 0)
break;
// 먹을 수 있는 물고기가 한 마리
if (fish_cnt == 1)
{
fish = bfs();
// 그 물고기를 먹으러 못 갈 수도 있다
if (fish.size() == 0)
break;
else
{
ans += fish[0].sigan;
shark.kosu++;
map[fish[0].hang][fish[0].yul] = 0;
shark.row = fish[0].hang;
shark.col = fish[0].yul;
evolve();
}
}
else
{
fish = bfs();
if (fish.size() == 0)
break;
else
{
// 조건에 맞게 정렬
sort(fish.begin(), fish.end());
ans += fish[0].sigan;
shark.kosu++;
map[fish[0].hang][fish[0].yul] = 0;
shark.row = fish[0].hang;
shark.col = fish[0].yul;
evolve();
}
}
memset(visited, false, sizeof(visited));
}
cout << ans << '\n';
return 0;
}
|
cs |