💡 구현/시뮬레이션
Memory 14592KB Time 32ms Code Length 5687B
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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
// 8:57 ~
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
struct loc {
int y, x;
};
vector<int> fish_map[4][4]; // 방향을 담음
vector<int> duplicate_map[4][4];
vector<int> smell_map[4][4];
loc Shark;
int M, S;
const int dy[] = { 0,-1,-1,-1,0,1,1,1 }; // 0 ~ 7 ←, ↖, ↑, ↗, →, ↘, ↓, ↙
const int dx[] = { -1,-1,0,1,1,1,0,-1 };
const int shark_dy[] = { -1,0,1,0 }; // 상 좌 하 우
const int shark_dx[] = { 0,-1,0,1 }; // 상 좌 하 우
void init() {
cin >> M >> S;
for (int i = 0; i < M; i++) {
int y, x, d;
cin >> y >> x >> d;
y--; x--; d--;
fish_map[y][x].push_back(d);
}
cin >> Shark.y >> Shark.x;
Shark.y--; Shark.x--;
}
void duplicate_start() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
duplicate_map[i][j] = fish_map[i][j];
}
}
}
void duplicate_end() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < duplicate_map[i][j].size(); k++) {
fish_map[i][j].push_back(duplicate_map[i][j][k]);
}
}
}
}
void fish_move() {
vector<int> new_fish_map[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < fish_map[i][j].size(); k++) {
// 물고기 이동
bool flag = false; // 가는 방향 찾아서 옮겼나?
for (int t = 0; t < 8; t++) {
int dir = (fish_map[i][j][k] - t + 8) % 8;
int ny = i + dy[dir];
int nx = j + dx[dir];
// 상어 있는칸, 물고기 냄새 있는칸, 격자 범위를 넘어나면 이동 불가능
if (ny >= 4 || nx >= 4 || ny < 0 || nx < 0) continue;
if (ny == Shark.y && nx == Shark.x) continue;
if (smell_map[ny][nx].size() > 0) continue;
flag = true;
new_fish_map[ny][nx].push_back(dir);
break;
}
if (flag == false) { // 이동 못하므로 제자리
new_fish_map[i][j].push_back(fish_map[i][j][k]);
}
}
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
fish_map[i][j] = new_fish_map[i][j];
}
}
}
// 초기화 해주어야함
int visited[4][4];
int bestdir = -1;
int bestcnt = -1;
void shark_dir_find(int depth, int y, int x, int cnt, int dir) {
if (depth == 3) {
if (bestcnt < cnt) {
bestdir = dir;
bestcnt = cnt;
}
else if (bestcnt == cnt) {
if (bestdir > dir) {
bestdir = dir;
}
}
return;
}
for (int i = 0; i < 4; i++) { // 상 좌 하 우 순서
int ny = y + shark_dy[i];
int nx = x + shark_dx[i];
if (ny >= 4 || nx >= 4 || ny < 0 || nx < 0) continue;
int fishnum = fish_map[ny][nx].size(); // 현재 칸에 있는 물고기 수
if (visited[ny][nx] >= 1) fishnum = 0;
visited[ny][nx] ++;
shark_dir_find(depth + 1, ny, nx, cnt + fishnum, dir * 10 + i);
visited[ny][nx] --;
}
}
void shark_move() {
memset(visited, 0, sizeof(visited));
bestdir = -1;
bestcnt = -1;
shark_dir_find(0, Shark.y, Shark.x, 0, 0);
int dir[3] = { 0 };
dir[0] = bestdir / 100;
bestdir %= 100;
dir[1] = bestdir / 10;
bestdir %= 10;
dir[2] = bestdir;
for (int i = 0; i < 3; i++) {
Shark.y += shark_dy[dir[i]];
Shark.x += shark_dx[dir[i]];
int died_fish = fish_map[Shark.y][Shark.x].size();
fish_map[Shark.y][Shark.x].clear();
// 냄새 추가
if (died_fish != 0) smell_map[Shark.y][Shark.x].push_back(0);
}
}
void smell_disappear() {
// 물고기 냄새가 2이상인것 제거 및 냄새 증가
vector<int> new_smell_map[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < smell_map[i][j].size(); k++) {
if (smell_map[i][j][k] >= 2) {
continue;
}
else {
// 냄새 증가
new_smell_map[i][j].push_back(smell_map[i][j][k] + 1);
}
}
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
smell_map[i][j] = new_smell_map[i][j];
}
}
}
void printMAP() {
cout << endl;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << fish_map[i][j].size() << " ";
}
cout << endl;
}
}
int cntFish() {
int cnt = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cnt += fish_map[i][j].size();
}
}
return cnt;
}
int main() {
init();
for (int i = 0; i < S; i++) {
// 아래 5번에서 물고기가 복제되어 칸에 나타남.(복제맵)
duplicate_start();
//printMAP();
// 물고기 이동
fish_move();
//printMAP();
// 상어의 연속 이동
shark_move();
//printMAP();
// 물고기의 냄새가 격자에서 사라짐. (냄새맵)
smell_disappear();
//printMAP();
//복제마법 완료.
duplicate_end();
//printMAP();
}
cout << cntFish() << endl;
}
//4x4 크기의 격자.(맵<vector>) 방향만 저장하면될듯
//1. 아래 5번에서 물고기가 복제되어 칸에 나타남.(복제맵)
//2. 물고기가 이동함.상어가 있는칸, 물고기 냄새가 있는 칸, 격자의 범위를 벗어나는칸은 이동 불가능
//각 물고기는 자신이 가지고 있는 이동 방향이 이동 할 수 있는 칸을 향할때 까지 45도 반시계회전, 이동할수 없다면 이동 x
//3. 상어가 연속해서 3칸 이동.상어는 상하좌우 인접칸 이동가능.연속해서 이동하는 칸중 격자의 범위를 벗어나면 불가능한 이동방법.제외되는 물고기는 냄새를 남김. (DFS(depth, y, x)) // 상 좌 하 우 순으로 우선순위를 가짐
//4. 두번전 연습에서 생긴 물고기의 냄새가 격자에서 사라짐. (냄새맵)
//5. 복제마법 완료.
//
//입력 : M(물고기의 수), S(연습횟수)
// M개의 줄에 y, x, d 주어짐 1~8 ←, ↖, ↑, ↗, →, ↘, ↓, ↙
// 상어의 위치 Sx Sy주어짐
//
// 출력 : S번의 연습을 마친 후 격자에 있는 물고기수
이 코드는 4x4 크기의 격자에 물고기와 상어가 있는 상황에서 주어진 조건에 따라 물고기와 상어를 이동시키고 상어가 물고기를 먹는 과정을 시뮬레이션하는 프로그램이다.
초기화: 물고기의 수(M)와 연습 횟수(S)를 입력받고, 각 물고기의 위치와 이동 방향을 저장한다.
물고기 이동: 각 물고기는 주어진 조건에 따라 이동하며, 상어가 있는 칸, 물고기 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다.
상어 이동: 상어는 연속해서 3칸을 이동하며, 상어가 먹을 수 있는 물고기의 수를 최대화하기 위해 DFS를 사용하여 상어의 이동 경로를 결정한다.
냄새 처리: 물고기의 냄새가 2이상인 경우 제거하고, 냄새를 증가시킨다.
복제 완료: 물고기의 이동이 끝나면 물고기들을 복제맵에 업데이트한다.
S번의 연습을 마친 후 격자에 남아있는 물고기 수를 출력한다.
이 프로그램은 주어진 조건에 따라 물고기와 상어의 이동을 시뮬레이션하여 최종적으로 남아있는 물고기의 수를 계산하는 것을 목표로 한다.
