16236 Samsung sw test
코드
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
#include <iostream>
#include <list>
#define MAX_WIDTH 20
using namespace std;
typedef struct Location {
int row;
int col;
int distance;
bool operator < (Location t) {
if (distance < t.distance)
return true;
else if (t.distance < distance)
return false;
else {
if (row < t.row)
return true;
else if (t.row < row)
return false;
else if (col < t.col)
return true;
else
return false;
}
}
} Location;
int map[MAX_WIDTH][MAX_WIDTH];
int width;
Location shark;
int babyShark();
bool isThereSmallThanMe(int sharkSize);
int main() {
cin >> width;
for (int i = 0; i < width; i++)
for (int j = 0; j < width; j++) {
cin >> map[i][j];
if (map[i][j] == 9) {
shark.row = i;
shark.col = j;
shark.distance = 0;
map[i][j] = 0;
}
}
cout << babyShark();
}
int babyShark() {
int distance = 0;
int sharkSize = 2;
int countEat = 0;
while (true) {
if (isThereSmallThanMe(sharkSize)) {
list<Location> q;
list<Location> canEat;
q.push_back(shark);
bool visit[MAX_WIDTH][MAX_WIDTH] = { 0, };
visit[shark.row][shark.col] = true;
while (!q.empty()) {
Location temp = q.front();
q.pop_front();
if (map[temp.row][temp.col] != 0 && map[temp.row][temp.col] < sharkSize)
canEat.push_back(temp);
if (temp.row > 0 && !visit[temp.row - 1][temp.col] && map[temp.row - 1][temp.col] <= sharkSize) {
q.push_back({ temp.row - 1, temp.col, temp.distance + 1 });
visit[temp.row - 1][temp.col] = true;
}
if (temp.col < width - 1 && !visit[temp.row][temp.col + 1] && map[temp.row][temp.col + 1] <= sharkSize) {
q.push_back({ temp.row, temp.col + 1, temp.distance + 1 });
visit[temp.row][temp.col + 1] = true;
}
if (temp.row < width - 1 && !visit[temp.row + 1][temp.col] && map[temp.row + 1][temp.col] <= sharkSize) {
q.push_back({ temp.row + 1, temp.col, temp.distance + 1 });
visit[temp.row + 1][temp.col] = true;
}
if (temp.col > 0 && !visit[temp.row][temp.col - 1] && map[temp.row][temp.col - 1] <= sharkSize) {
q.push_back({ temp.row, temp.col - 1, temp.distance + 1 });
visit[temp.row][temp.col - 1] = true;
}
}
//가장 가깝고 왼쪽 위 먹고, visit 초기화, shark 위치, 사이즈 확인, count 1 증가,
if (!canEat.empty()) {
canEat.sort();
Location eat = canEat.front();
map[eat.row][eat.col] = 0;
shark.row = eat.row;
shark.col = eat.col;
shark.distance = 0;
distance += eat.distance;
countEat++;
if (countEat == sharkSize) {
sharkSize++;
countEat = 0;
}
}
else
break;
}
else
break;
}
return distance;
}
bool isThereSmallThanMe(int sharkSize) {
for (int i = 0; i < width; i++)
for (int j = 0; j < width; j++)
if (map[i][j] != 0 && sharkSize > map[i][j])
return true;
return false;
}