https://www.acmicpc.net/problem/19237
19237번: 어른 상어
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미
www.acmicpc.net
바보같이 3번 틀린 문제, M을 N으로 쓰는..바보같은 짓을 했다.
코드의 진행과정은 다음과 같다.
MAP과 Shark 구조체 선언
MAP에는 smell_count와 size 즉 상어의 크기,
Shark에는 x, y, dir, 우선순위 방향, 생사 유무가 저장되어있다.
input에서부터 고민하게 되는 문제이다.
N,M,K를 입력 받은 후 MAP의 정보를 입력 받는다. 이때 상어의 위치도 같이 저장.
그 다음 상어의 방향을 입력 받을때는 상어의 생사 유무도 입력받는다.
그 다음은 상어의 방향 우선순위이다, 방향은 Shark 구조체 안에 [5][5] 배열을 넣어줘서 사용한다.
solve 함수는 4가지 함수로 돌아간다.
첫번째 move 함수,
상어가 움직일 수 있는 위치를 확인한다. 그리고 shark_info 배열에 바뀐 위치와 방향을 저장
이때 map은 건드리지않는다.
두번째 kill_and_move함수
상어가 맵에서 움직이는 함수이다. 움직일때 1번부터 순서대로 이동하므로, 만약 이동하는 칸에 상어가 있으면,
그 상어는 숫자가 작은 함수 이므로, 늦게 움직이는 상어는 죽는다.
세번째는 smell_processing함수
상어의 냄새를 처리 하는 함수, 처음에는 bfs로 냄새의 위치를 탐색 할려 했지만, 맵이 20*20이므로, 그냥 모두 확인
냄새를 다 -- 해준다, 그리고 이동한 곳의 냄새는 K로 초기화한다,
네번째는 모두 false인지 check하는 함수이다.
여기서 M을 N으로 써서 4번틀림 ㅇㅇ
전체 코드는 다음과 같다.
|
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
|
#include <iostream>
#include <deque>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
struct MAP {
int smell_count;
int size;
};
struct Shark {
int x, y;
int dir;
int prior_dir[5][5];
bool alive;
};
// 위 아래 왼쪽 오른쪽
int dx[5] = { 0,-1,1,0,0 };
int dy[5] = { 0,0,0,-1,1 };
// 변수들
int N, M, K;
Shark SHARK_INFO[401];
MAP MAP_INFO[21][21];
// 냄새가 있는 좌표 관리
bool check_range(int& next_x, int& next_y) {
if (next_x >= 1 && next_y >= 1 && next_x <= N && next_y <= N)
return true;
else
return false;
}
bool check_shark() {
for (int i = 2; i <= M; i++) {
if (SHARK_INFO[i].alive == true) {
return false;
}
}
return true;
}
void smell_Processing() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (MAP_INFO[i][j].smell_count != 0) {
MAP_INFO[i][j].smell_count--;
if (MAP_INFO[i][j].smell_count == 0) {
MAP_INFO[i][j].size = 0;
}
}
}
}
for (int i = 1; i <= M; i++) {
if (SHARK_INFO[i].alive == false)
continue;
int x = SHARK_INFO[i].x;
int y = SHARK_INFO[i].y;
MAP_INFO[x][y].size = i;
MAP_INFO[x][y].smell_count = K;
}
}
void kill_and_move() {
for (int i = 1; i <= M; i++) {
if (SHARK_INFO[i].alive == false)
continue;
int x = SHARK_INFO[i].x;
int y = SHARK_INFO[i].y;
//cout << SHARK_INFO[i].x << SHARK_INFO[i].y << endl;
if (MAP_INFO[x][y].size == 0 || MAP_INFO[x][y].size == i)
MAP_INFO[x][y].size = i;
else
SHARK_INFO[i].alive = false;
}
}
void move() {
for (int i = 1; i <= M; i++) {
if (SHARK_INFO[i].alive == false)
continue;
// 처음에는 우선 순위로 빈칸 이동 확인하기
int dir = SHARK_INFO[i].dir;
bool flag = false;
for (int j = 1; j <= 4; j++) {
int next_x = SHARK_INFO[i].x + dx[SHARK_INFO[i].prior_dir[dir][j]];
int next_y = SHARK_INFO[i].y + dy[SHARK_INFO[i].prior_dir[dir][j]];
if (check_range(next_x, next_y) && MAP_INFO[next_x][next_y].size == 0) {
SHARK_INFO[i].dir = SHARK_INFO[i].prior_dir[dir][j];
SHARK_INFO[i].x = next_x;
SHARK_INFO[i].y = next_y;
flag = true;
break;
}
}
if (flag == true)
continue;
// 자기 냄새 칸으로 우선 순위 지켜서 이동
for (int j = 1; j <= 4; j++) {
int next_x = SHARK_INFO[i].x + dx[SHARK_INFO[i].prior_dir[dir][j]];
int next_y = SHARK_INFO[i].y + dy[SHARK_INFO[i].prior_dir[dir][j]];
if (check_range(next_x, next_y) && MAP_INFO[next_x][next_y].size == i) {
SHARK_INFO[i].dir = SHARK_INFO[i].prior_dir[dir][j];
SHARK_INFO[i].x = next_x;
SHARK_INFO[i].y = next_y;
break;
}
}
}
}
void solve() {
// 이동 할 칸 확인하기
int day = 0;
while (day < 1000){
day++;
move();
kill_and_move();
smell_Processing();
if (check_shark() == true) {
cout << day << endl;
return;
}
}
cout << -1 << endl;
}
void input() {
cin >> N >> M >> K;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> MAP_INFO[i][j].size;
if (MAP_INFO[i][j].size != 0) {
SHARK_INFO[MAP_INFO[i][j].size].x = i;
SHARK_INFO[MAP_INFO[i][j].size].y = j;
MAP_INFO[i][j].smell_count = K;
}
}
}
for (int i = 1; i <= M; i++) {
cin >> SHARK_INFO[i].dir;
SHARK_INFO[i].alive = true;
}
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= 4; j++) {
for (int k = 1; k <= 4; k++) {
cin >> SHARK_INFO[i].prior_dir[j][k];
}
}
}
}
void init() {
ios::sync_with_stdio(false);
cin.tie(0);
}
int main() {
init();
input();
solve();
}
|
cs |
'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글
| [백준 3190] 뱀 (C++) (0) | 2021.08.21 |
|---|---|
| [백준 1092] 배 (C++) (0) | 2021.08.21 |
| [백준 17090] 미로 탈출하기 (C++) (0) | 2021.08.20 |
| [백준 14890] 경사로 (C++) (0) | 2021.08.20 |
| [백준 19236] 청소년 상어 (C++) (0) | 2021.08.19 |