💡 구현/시뮬레이션
Memory 2592KB Time 160ms Code Length 5640B
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
194
195
196
197
198
199
200
201
202
203
// 상어는 고유 번호가 있따.
// 1번 상어가 대빵, 다쫓아냄
// 1. 자신의 위치에서 냄새 뿌리기
// 2. 상어의 동시 이동 자신의 냄새를 해당칸에 뿌림
// 3. 냄새는 상어가 k번 이동하면 사라짐
// 이동 방향 결정할 때는, 인접한 칸 중에 아무냄새가 없는 칸의 방향으로 잡고, 그런칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡음.
// 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고있는 방향에 따라 다를 수 도 있다.
// 우선순위는 주어짐.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int N, M, K;
struct info_map {
int num, dir;
};
struct info_smell {
int num;
int cnt; // 머무른 횟수
};
info_map shark_map[20][20] = {0};
vector<info_smell> smell_map[20][20];
int priority_map[401][4][4];
const int dy[] = {-1, 1, 0,0};
const int dx[] = {0, 0, -1, 1}; // 위(0), 아래(1), 왼쪽(2), 오른쪽(3)
void init() {
cin >> N >> M >> K; // 맵크기, 상어수, 냄새 사라지는 시간
for (int i = 0; i < N; i++) { // 상어 번호 배치 맵에 반영
for (int j = 0; j < N; j++) {
cin >> shark_map[i][j].num;
}
}
for (int k = 1; k <= M; k++) { // 상어 방향 맵에 반영
int tmp_dir;
cin >> tmp_dir;
for (int i = 0; i < N; i++) { //
for (int j = 0; j < N; j++) {
if (shark_map[i][j].num == k) {
shark_map[i][j].dir = tmp_dir - 1; // 0~3
}
}
}
}
for (int i = 1; i <= M; i++) { // 우선순위
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
int dir;
cin >> dir;
priority_map[i][j][k] = dir -1;
}
}
}
}
void spreadSmell() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (shark_map[i][j].num != 0) {
smell_map[i][j].push_back({ shark_map[i][j].num , 0 });
}
}
}
}
void moveshark() {
info_map new_map[20][20]; // 동시 진행 하므로 현재맵을 보고 새로운 맵을 생성함.
memset(new_map, 0, sizeof(new_map));
// 상어의 현재 바라보고 있는 방향에 따라 다음 방향의 순서가 결정됨.
// 이동 방향 결정할 때는, 인접한 칸 중에 아무냄새가 없는 칸의 방향으로 잡고, 그런칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡음.
// 해당 방향에 상어가 있을 때 상어 번호가 더 작다면 덮어씌우기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (shark_map[i][j].num != 0) {
info_map shark = shark_map[i][j];
// 아무 냄새 없는 칸의 방향 찾기
bool flag = false;
for (int k = 0; k < 4; k++) {
int ny = i + dy[priority_map[shark.num][shark.dir][k]];
int nx = j + dx[priority_map[shark.num][shark.dir][k]];
if (ny >= N || nx >= N || ny < 0 || nx < 0) continue;
if (smell_map[ny][nx].size() != 0) continue;
flag = true;
// 옮겨진 위치를 새로운 맵에서 갱신
shark.dir = priority_map[shark.num][shark.dir][k]; // 방향 갱신
if (new_map[ny][nx].num == 0 || new_map[ny][nx].num > shark.num) { // 빈칸이거나 기존에 있던 놈 보다 수가 작아야함
new_map[ny][nx] = shark; // 맵에서 갱신
}
break;
}
if (!flag) {
for (int k = 0; k < 4; k++) {
int ny = i + dy[priority_map[shark.num][shark.dir][k]];
int nx = j + dx[priority_map[shark.num][shark.dir][k]];
if (ny >= N || nx >= N || ny < 0 || nx < 0) continue;
bool findsmell = false;
for (int t = 0; t < smell_map[ny][nx].size(); t++) {
if (smell_map[ny][nx][t].num == shark.num) {
findsmell = true;
break;
}
}
if (!findsmell) continue;
// 옮겨진 위치를 새로운 맵에서 갱신
shark.dir = priority_map[shark.num][shark.dir][k]; // 방향 갱신
if (new_map[ny][nx].num == 0 || new_map[ny][nx].num > shark.num) { // 빈칸이거나 기존에 있던 놈 보다 수가 작아야함
new_map[ny][nx] = shark; // 맵에서 갱신
}
break;
}
}
}
}
}
memcpy(shark_map, new_map, sizeof(shark_map));
}
void removeSmell() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
vector<info_smell> nextSmell;
int size = smell_map[i][j].size();
for (int k = 0; k < size; k++) {
if (smell_map[i][j][k].cnt < K) { // K보다 작을 때만 다시 추가해줌.
nextSmell.push_back(smell_map[i][j][k]);
}
}
smell_map[i][j] = nextSmell;
}
}
}
void plusSmellTime() {
// 냄새 시간 증가
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int size = smell_map[i][j].size();
for (int k = 0; k < size; k++) {
smell_map[i][j][k].cnt += 1;
}
}
}
}
bool checkmap() {
int sum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (shark_map[i][j].num != 0) {
sum += shark_map[i][j].num;
}
}
}
if (sum == 1) return true;
else return false;
}
void printmap() {
cout << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << shark_map[i][j].num << " ";
}
cout << endl;
}
}
int main() {
init();
int time = 0;
while (1) {
// 1번 상어만 격자에 남아 있다면 break;
if (checkmap()) {
break;
}
// time이 1000을 넘는다면 break;
if (time >= 1000) {
time = -1;
break;
}
// 1. 자신의 위치에서 냄새 뿌리기
spreadSmell();
// 2. 상어의 동시 이동
moveshark();
// 3. 냄새 시간 증가
plusSmellTime();
// 4. 냄새 k번 이동하면 사라짐
removeSmell();
time++;
//printmap();
}
cout << time;
}
이 코드는 상어들이 격자 안에서 움직이는 시뮬레이션을 수행하는 프로그램이다.
먼저 초기화(init) 함수에서 격자의 크기(N), 상어의 수(M), 냄새가 사라지는 시간(K)을 입력받고, 상어들의 위치와 방향, 각 상어의 이동 우선순위를 설정한다.
spreadSmell 함수에서는 각 상어가 있는 위치에 냄새를 뿌린다.
moveshark 함수에서는 각 상어를 동시에 이동시키는데, 상어는 인접한 칸 중에 냄새가 없는 칸의 방향으로 이동하며, 만약 그런 칸이 없다면 자신의 냄새가 있는 칸의 방향으로 이동한다. 상어가 이동한 후에는 새로운 맵에 상어의 위치를 갱신한다.
removeSmell 함수에서는 냄새가 사라지는 시간이 지난 냄새를 제거한다.
plusSmellTime 함수에서는 남아있는 냄새들의 시간을 증가시킨다.
checkmap 함수에서는 1번 상어만 격자에 남아있는지 확인하여 게임을 종료할지 여부를 결정한다.
main 함수에서는 위의 함수들을 이용하여 시뮬레이션을 반복하고, 1번 상어만 남아있거나 시간이 1000을 넘으면 종료한다. 종료 시간을 출력한다.
시간이 1000이상이면 종료하는 것 때문에… 지문 오해를 했다. 3시간만 버렸다.
