알고리즘/백준 BAEK JOON
19237.어른상어
IMyoungho
2020. 9. 17. 00:12
이번에 풀어볼 문제 역시 따끈따끈한 최신문제 백준의 19237 어른상어이다.
19237번: 어른 상어
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미
www.acmicpc.net
예전에 아기상어라는 문제를 푼적이 있는데 백준에 어른상어와 청소년상어가 추가되었다.
그 중 어른상어의 문제이다. 난이도는 복잡한 구현만 해결하면 충분히 풀 수 있는 거같다.
시간이 좀 오래걸렸지만 큰 틀(완성직전)까지는 나쁘지않은 시간이 걸린거 같다.
다만 예외처리까지 설계하는 힘은 아직 부족한거 같다. 이 문제는 왜인지 모르게 로봇청소기 문제가 떠올랐다.
그리고 문제를 완성한 뒤, 디버깅해보니 진짜 상어가 뭔가 살아 움직이는 느낌이 들어서 재밌었다.
데이터를 입력받는 부분들은 수월하게 가능했고 상어가 이동하면 냄새의 시간이 줄어드는 부분과
상어의 이동들도 굉장히 순탄하게 구현했다. 내가 애를 조금 먹은 부분은 상어의 이동 방향이다.
딱, 한가지 조건에서 내 수준에서의 효율적인 코드를 생각하지 못했는데,
바로 4방향 탐색 후, 갈 곳이 없다면 자신의 냄새 방향으로 가는 것이다.
사실 이 조건이 문제가 아니라 그냥 전체적으로 로직상의 문제라고 생각하는게 더빠른거같다.
=> 처음 풀이이다..
해당 문제는 상당히 어려웠다고 생각한다. 그 이유는 구현이 어려운거보다 설계가 어려웠다.
생각해내지 못하면 해결할 수 없는 미궁에 빠진다..
거의 다풀기 직전에서 자꾸 막혀서 여러번 다지우고 다시 시도했는데 항상 같은 부분에서 막혔고
그 부분은 상어의 빈칸 또는 상어를 잡어먹는 부분이었다.
결국 다른 분의 블로그를 참조해서 풀었다. yabmoons.tistory.com/496#comment15909706
해당 내용의 풀이는 다음과 같다.
1. spread 함수
상어의 냄새를 뿌려주고 해당 냄새의 주인을 지정하는 함수 구현
저장된 상어정보의 좌표를 가져와서 냄새의 주인과 냄새를 뿌려준다. ( 좌표를 가져와서 판단하는 것도 중요한 point다 )
중요한 점은 진행된 시간이 기준이 되는 것이다( 이 부분을 나는 생각하지 못했다 )
2. move 함수
상어 이동함수로 map의 공간에 상어를 넣는다.
주의할 점은 해당 공간의 주인을 정하는 함수는 spread함수이지 move 함수가 아니다.
move 함수는 해당 공간에 상어를 넣어주기만하고 중복되지 않는 경우 spread 함수에서 주인이된다.
중복되는 경우 eat함수에서 제거가 된다.
현재 시간에서 냄새의 시간이 현재시간보다 작거나 같은 좌표로 이동한다.
1. 만약 갈 수 있는 곳이 있다면 해당 좌표와 방향을 저장하고 해당 좌표 공간에 상어번호를 저장한다.
갈 수 있는 곳을 탐색하면서 자신의 냄새 좌표를 혹시모르니 미리 저장해둔다.
=> 이 때 중요한 것은 임시좌표를 -1로 초기화 해주어서 해당 -1이 변환되면
이미 자기냄새를 찾은 것이므로 pass하는 로직이 필요하다. ( 86, 106 라인 참고 )
=> 이걸 하지 않으면 자신의 냄새가 주변에 여러개 있을 때 우선순위가 느린 좌표가 저장된다..
2. 갈수 있는 곳이 없다면 자신의 냄새좌표로 이동한다.
3. eat 함수
한 공간에 여러 상어가 존재할 시, 번호가 작은 상어가 나머지 상어를 모두 잡아먹는다.
이 경우 제일 번호가 작은 상어를 제외하고 모두 제거한다. 그리고
해당 내용이 끝나면 다시 spread 함수가 진행되면서 해당 공간의 냄새의 주인이 결정되므로
공간에 저장된 모든 상어를 제거해줘야한다. -> 다음 move 함수의 탐색을 위해서..
move에서 빈칸을 찾아가는 기준이 map에 저장된 상어 냄새의 주인이나 빈칸의 여부가 아닌 갈 수있는지 판단하는 시간이므로
< 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
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
|
#pragma warning(disable:4996) #include <iostream>
#include <vector>
#include <algorithm>
#define MAX 21
#define MAX2 401
using namespace std;
int dx[5] = { 0, -1, 1, 0, 0 };
int dy[5] = { 0, 0, 0, -1, 1 };
struct shark{
int x, y, dir; // 좌표 및 방향 변수
bool life; // 생존여부 변수
vector<int>p[5]; // 우선순위 vector
};
struct info{ // map 정보
int smell, shark; // 몇초뒤에 갈 수있는지에 대한 냄새 변수, 해당 냄새의 주인
vector<int>s; // 해당 공간에 존재하는 상어 저장 vector
};
int N, M, K;
info map[MAX][MAX]; // map 정보에 대한 배열
shark sk[MAX2]; // 상어 정보에 대한 배열
int die, ans; // 죽은 상어 카운트 변수, 정답 변수
void showme(){ // 디버깅 함수
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cout << map[i][j].shark << " ";
}
cout << endl;
}
cout << endl;
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cout << map[i][j].smell << " ";
}
cout << endl;
}
cout << endl;
}
void eat(){ // 상어를 잡아먹는 함수
for (int i = 1; i <= M; i++){
if (!sk[i].life) // 죽은 상어는 탐색 제외
continue;
int x = sk[i].x;
int y = sk[i].y;
if (map[x][y].s.size() >= 2){ // 2개이상이라는 의미 => 같은 칸에 여러 상어가 존재하는 경우
sort(map[x][y].s.begin(), map[x][y].s.end()); // 오름차순으로 정렬
//map[x][y].shark = map[x][y].s.front();// 제일 앞에 있는 상어의 번호가 가장 작기떄문에 해당 내용이 해당 칸을 차지한다. 굳이 필요는 없음 이유는 먹히고나면 탐색에서 제외되기 때문이다.
for (int j = 1; j < map[x][y].s.size(); j++){ // 제일 앞을 제외한 나머지 중복 상어들 확인
sk[map[x][y].s[j]].life = false; // 나머지 상어들은 잡아먹음
die++; // 잡아먹힌 상어수 +1
//cout << "[-] "<< map[x][y].s[j] << " shark is dead " << endl;
}
map[x][y].s.clear(); // 해당 좌표의 주인상어가 정해졌으므로 해당 겹치는 구간 제거
}
}
for (int i = 1; i <= M; i++){ // 상어가 중복 있던 좌표들은 이미 주인이 정해졌으므로
if (!sk[i].life) // 죽은 상어는 탐색 제외
continue;
int x = sk[i].x;
int y = sk[i].y;
map[x][y].s.clear(); // 잡아먹어서 죽은 상어 외에도 나머지 상어들도 다음 탐색을 위해 중복 칸에 대한 내용을 모두 비움
}
}
void move(int time){
for (int i = 1; i <= M; i++){ // 그리고 다시 이동 하면서 중복칸에 대한 내용을 채워감
if (!sk[i].life) // 죽은 상어는 탐색 제외
continue;
int x = sk[i].x; // 해당 상어의 좌표 변수
int y = sk[i].y; // 해당 상어의 좌표 변수
int dir = sk[i].dir; // 해당 상어의 방향 변수
bool flag = false; // 빈칸을 발견했는지에 대한 유무 변수
int tmp_x, tmp_y, tmp_dir; // 4방향 탐색 중에 자신과 같은 냄새 발견시에 미리 저장해둠
tmp_x = tmp_y = tmp_dir = -1; // -1로 초기화 -> 임시 저장한적이 있는지 없는지 판단을 위해
// 이유는 이걸 구별해주지 않으면 나와 같은 냄새가 여러곳에 있을 때 이미 우선순위로 찾았는데도
// 불구하고 제일 우선순위가 느린 녀석이 덮어쓰임
for (int j = 0; j < 4; j++){ // 4방향 탐색 ( 해당 상어의 우선순위 방향으로 4방향 탐색 )
int ax = x + dx[sk[i].p[dir][j]]; // 우선순위 기준 4방향
int ay = y + dy[sk[i].p[dir][j]]; // 우선순위 기준 4방향
if (ax < 0 || ay < 0 || ax >= N || ay >= N) // 범위초과시 탐색 pass
continue;
if (map[ax][ay].smell <= time){ // 해당 smell 변수는 해당 시간 이후부터 갈 수 있는 공간(빈공간이되므로)이므로
flag = true; // 빈칸 발견했으므로 flag true
sk[i].x = ax; // 냄새가 사라져서 갈 수 있는 칸인 경우 해당 좌표 저장
sk[i].y = ay; // 냄새가 사라져서 갈 수 있는 칸인 경우 해당 좌표 저장
sk[i].dir = sk[i].p[dir][j]; // 빈칸을 찾은 방향 저장
map[ax][ay].s.push_back(i); // 해당 공간에 상어 번호 저장 -> 해당좌표의 냄새의 주인은 해당공간에 중복이 없을 시, spread 함수에서 결정됨
break;
}
else if (map[ax][ay].shark == i){ // 자신과 같은 냄새 발견시 혹시 모르니 좌표 저장
if (tmp_x == -1){// 자신과 같은 냄새를 발견했는데 아직 임시저장한 적이 없다면 => 임시저장한 적이 있다면 이미 우선순위중 가장 빠른 자기 냄새 정보가 저장됨
tmp_x = ax; // 자신의 냄새 좌표 미리 저장
tmp_y = ay; // 자신의 냄새 좌표 미리 저장
tmp_dir = sk[i].p[dir][j]; // 자신의 냄새 방향 미리 저장
}
}
}
if (!flag){ // 빈칸을 발견하지 못했을 때(4방향 탐색에도 갈 곳이 없을때)
map[tmp_x][tmp_y].s.push_back(i); // 해당 공간에 상어번호 저장
sk[i].x = tmp_x; // 미리 저장해놓은 자신의 냄새쪽 좌표로 이동
sk[i].y = tmp_y; // 미리 저장해놓은 자신의 냄새쪽 좌표로 이동
sk[i].dir = tmp_dir; // 미리저장해놓은 자신의 방향으로 정보 변경
}
}
}
void spread(int time){ // 냄새 뿌리는 함수
for (int i = 1; i <= M; i++){
if (!sk[i].life) // 죽은 상어 탐색 제외
continue;
int x = sk[i].x;
int y = sk[i].y;
map[x][y].shark = i; // 해당 냄새의 주인 저장
map[x][y].smell = time + K; // 해당 냄새가 몇초 후에 사라질 것인지 저장
}
}
void search(){// 큰 틀에서의 함수
int time = 0; // 시간을 카운트하기위한 변수
while (time <=1000){ // 1000을 넘지 않는 선에서 시간 카운트
if (die == M-1){ // 상어가 1마리남으면
ans = time; // 해당 시간 저장 후 종료
break;
}
spread(time); // 냄새를 뿌리고 해당 칸의 냄새주인을 저장하는 함수
//showme(); // 디버깅
move(time); // 상어 움직이는 함수
eat(); // 겹치는 상어 잡아먹는 함수
time+=1; // 시간 카운트 +1
}
if (time == 1001) // 1000보다 크면
ans = -1; // -1 출력을 위해 저장
}
int main(){
freopen("19237.txt","r",stdin);
cin >> N >> M >> K;
int shark;
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cin >> shark;
if (shark != 0){
sk[shark] = { i, j, 0, true };
}
}
}
int dir;
for (int i = 1; i <= M; i++){
cin >> dir;
sk[i].dir = dir;
}
int tmp;
for (int i = 1; i <= M; i++){
for (int j = 1; j <= 4; j++){
for (int z = 0; z < 4; z++){
cin >> tmp;
sk[i].p[j].push_back(tmp);
}
}
}
search();
cout << ans << endl;
return 0;
}
|
cs |
< Code 설명 2020.10.17 >
|
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
190
191
192
193
|
#pragma warning(disable:4996) #include <iostream>
#include <string.h>
#include <vector>
#define MAX 21
using namespace std;
int N, M, K;
int dx[5] = {0,-1,1,0,0};
int dy[5] = {0,0,0,-1,1};
struct fish{
int x, y, dir;
bool life;
vector<int>pri[5];
};
struct info{
int master;
int time;
vector<int>temp;
};
info map[MAX][MAX];
fish shark[MAX * MAX];
int shark_cnt;
void showme(){
cout << "shark-------------------------" << endl;
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
cout << map[i][j].master << " ";
}
cout << "\n";
}
cout << "\n";
cout << "smell time-------------------------" << endl;
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
cout << map[i][j].time << " ";
}
cout << "\n";
}
cout << "\n";
}
void move(){
int cnt = 0;
for (int i = 1; i <= M; i++){
if (shark[i].life){
int x = shark[i].x;
int y = shark[i].y;
int dir = shark[i].dir;
for (int j = 0; j < 4; j++){
int ax = x + dx[shark[i].pri[dir][j]];
int ay = y + dy[shark[i].pri[dir][j]];
if (ax <= 0 || ay <= 0 || ax > N || ay > N){
cnt++;
continue;
}
if (map[ax][ay].master == 0){
map[ax][ay].temp.push_back(i);
shark[i].x = ax;
shark[i].y = ay;
shark[i].dir = shark[i].pri[dir][j];
cnt = 0;
break;
}
cnt++;
}
if (cnt >= 4){
for (int j = 0; j < 4; j++){
int ax = x + dx[shark[i].pri[dir][j]];
int ay = y + dy[shark[i].pri[dir][j]];
if (ax <= 0 || ay <= 0 || ax > N || ay > N)
continue;
if (map[ax][ay].master == i){
map[ax][ay].temp.push_back(i);
shark[i].x = ax;
shark[i].y = ay;
shark[i].dir = shark[i].pri[dir][j];
break;
}
}
}
}
}
}
void spread(){
for (int i = 1; i <= M; i++){
if (shark[i].life){
int x = shark[i].x;
int y = shark[i].y;
map[x][y].time = K;
}
}
}
void eat(){
for (int i = 1; i <= M; i++){
if (shark[i].life){
int x = shark[i].x;
int y = shark[i].y;
int ans = 987654321;
for (int t = 0; t < map[x][y].temp.size(); t++){
if (map[x][y].temp[t] < ans)
ans = map[x][y].temp[t];
}
for (int t = 0; t < map[x][y].temp.size(); t++){
if (map[x][y].temp[t] != ans){
shark[map[x][y].temp[t]].life = false;
shark_cnt--;
}
}
map[x][y].master = ans;
map[x][y].time = K;
map[x][y].temp.clear();
}
}
}
void time_is_gone(){
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
if (map[i][j].time == 0)
map[i][j].master = 0;
if (map[i][j].time >= 1){
map[i][j].time -= 1;
}
}
}
}
void solve(){
int flag = false;
for (int t = 0; t <= 1000; t++){
if (shark_cnt == 1){
cout << t << endl;
flag = true;
break;
}
spread();
time_is_gone();
move();
eat();
//showme();
}
if (!flag)
cout << -1 << endl;
}
int main() {
freopen("19237.txt", "r", stdin);
cin >> N >> M >> K;
int num;
shark_cnt = M;
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
cin >> num;
if (num >= 1){
map[i][j].master = num;
shark[num] = {i,j,0,true};
}
}
}
int tmp;
for (int i = 1; i <= M; i++){
cin >> tmp;
shark[i].dir = tmp;
}
int a, b, c, d;
for (int i = 1; i <= M; i++){
for (int j = 1; j <= 4; j++){
cin >> a >> b >> c >> d;
shark[i].pri[j].push_back(a);
shark[i].pri[j].push_back(b);
shark[i].pri[j].push_back(c);
shark[i].pri[j].push_back(d);
}
}
solve();
return 0;
}
|
cs |
반응형