반응형
문제 링크: https://www.acmicpc.net/problem/23290
23290번: 마법사 상어와 복제
첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향
www.acmicpc.net
<문제 풀이> 시뮬레이션, 중복 순열, DFS
이 문제는 실수할 여지가 많았습니다. 저는 1번에서 5번을 순서대로 함수로 구현했습니다. 다음 함수 구현으로 넘어가기 전에 함수를 먼저 테스트하고 넘어갔습니다. 함수를 만들 때마다 테스트를 했던 방식이 실수를 줄이는 데 도움이 많이 되었던 것 같습니다.
0. 물고기, 상어, 냄새 표현하기
물고기는 격자에 여러 마리가 존재할 수 있기 때문에 vector형 2차원 배열을 만들었습니다.
상어는 한 마리만 존재할 수 있기 때문에 bool형 2차원 배열을 만들었습니다.
격자에 생성된 냄새가 몇 번째 연습 때 생성된 냄새인지를 표현하기 위해서 int형 2차원 배열을 만들었습니다.
vector<int> fish[5][5];
bool shark[5][5];
int smell[5][5]; //몇 번째 연습 때 생성된 냄새인지 저장
1. 모든 물고기를 복제한다. 5번에서 실제 복제가 된다.
이 부분은 간단히 연습이 시작될 때마다 격자판에 있는 물고기들을 백업해 두면 됩니다.
//1. 모든 물고기를 복제한다. 5번에서 실제 복제가 된다.
void backupFish() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
clonedFish[i][j] = fish[i][j];
}
}
}2. 모든 물고기가 한 칸 이동한다.
물고기가 이동한 정보를 배열에 반영할 때 바로 반영하면 물고기가 두 번 이상 움직일 수도 있습니다. 현재 바라보는 격자 칸이 (x, y) 일 때 해당 격자에서 이동한 물고기가 (x2,y2)로 이동했다고 하면, 다음 바라보는 격자가 (x2,y2) 일 때 이동했던 물고기가 한 번 더 이동하게 되기 때문입니다.
따라서 임시 배열에 물고기의 이동 정보들을 저장해두고 모든 물고기가 이동을 완료했으면 그때 원본 배열에 다시 저장해 두었습니다.
반시계 방향 전환은 단순히 방향값을 1씩 감소하면 되고, 최대 7번까지 방향 전환을 해보면 됩니다.
const int fishDx[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1}; // 물고기 방향 1 ~ 8
const int fishDy[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
vector<int> fish[5][5];
vector<int> movedFish[5][5]; // 물고기 이동 후
bool shark[5][5];
int smell[5][5]; //몇 번째 연습 때 생성된 냄새인지 저장
//2. 모든 물고기가 한 칸 이동한다.
void moveFish() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (auto dir : fish[i][j]) {
int cnt = 8; // 최대 7번까지 반시계 방향으로 회전해볼 수 있다.
bool moved = false;
int tempDir = dir;
while (cnt--) {
int nx = i + fishDx[tempDir];
int ny = j + fishDy[tempDir];
// 격자 범위를 벗어나는 칸, 상어가 있는 칸, 물고기의 냄새가 있는 칸이면 이동할 수 없다.
if (nx < 1 || ny < 1 || nx> N || ny > N || shark[nx][ny] || smell[nx][ny]) {
tempDir--; //반시계 방향으로 회전
if (tempDir == 0) tempDir = 8;
continue;
}
// 그 외의 경우에는 그 칸으로 이동한다.
moved = true;
movedFish[nx][ny].push_back(tempDir);
break;
}
if (!moved) movedFish[i][j].push_back(dir); //이동할 수 있는 칸이 없으면 이동 X
}
}
}
// 물고기들의 이동 정보를 실제로 반영
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
fish[i][j] = movedFish[i][j];
}
}
}
3. 상어가 연속해서 3칸 이동한다.
상어의 현재 위치에서 중복 순열 DFS로 상어가 이동할 수 있는 연속된 3칸을 구하면 됩니다. 중복 순열 DFS는 사전순으로 먼저 찾기 때문에 각 경우의 수에서 물고기가 더 많아졌을 때 상어가 이동한 좌표들을 업데이트하면 됩니다.
상어는 [상, 하, 상]처럼 이미 방문했던 좌표라도 다시 방문할 수 있습니다. 이때 다시 방문한 곳에 있는 물고기를 중복해서 먹지 않도록 DFS의 base case(k===3) 일 때 방문체크 배열을 만들어서 중복 부분을 처리해줘야 합니다.
DFS로 상어가 이동할 수 있는 좌표들을 구했으면 실제로 배열에 업데이트를 해야 합니다. 이때 상어가 이동한 칸에 물고기가 존재하면 물고기 냄새를 남겨야 합니다.
물고기 냄새는 현재까지 진행한 연습 횟수를 값으로 저장했습니다. 나중에 4번에서 두 번 전 연습에서 생긴 물고기를 제거할 때 if(현재까지 진행한 연습 횟수 - smell[i][j] == 2)가 되는 경우를 찾아 제거해 주면 됩니다.
const int sharkDx[5] = {0, -1, 0, 1, 0}; // 상어 방향 1 ~ 4
const int sharkDy[5] = {0, 0, -1, 0, 1};
vector<int> fish[5][5];
pair<int, int> tempMovedShark[3];
pair<int, int> movedShark[3]; // 상어가 이동한 좌표
int maxFishCnt = -1;
bool shark[5][5];
int smell[5][5]; //몇 번째 연습 때 생성된 냄새인지 저장
int t = 0; // 현재까지 진행한 연습 횟수
// 3. 상어가 연속해서 3칸 이동한다.
void moveSharkDFS(int x, int y, int k) {
if (k == 3) { // 상어가 3칸 이동
int fishCnt = 0;
bool visited[5][5]; //상어가 이미 먹은 물고기를 중복해서 먹지 않도록 방문 체크
fill(&visited[0][0], &visited[4][5], false);
for (int i = 0; i < k; i++) {
auto cur = tempMovedShark[i];
if (!visited[cur.X][cur.Y]) {
fishCnt += fish[cur.X][cur.Y].size();
visited[cur.X][cur.Y] = true;
}
}
// 중복 순열 DFS는 사전순으로 먼저 찾기 때문에 각 경우의수에서 물고기가 더 많아졌는지만 판단하면 된다.
if (fishCnt > maxFishCnt) {
maxFishCnt = fishCnt;
for (int i = 0; i < k; i++) {
movedShark[i] = tempMovedShark[i];
}
}
return;
}
for (int dir = 1; dir <= 4; dir++) {
int nx = x + sharkDx[dir];
int ny = y + sharkDy[dir];
if (nx < 1 || ny < 1 || nx > N || ny > N) continue; //격자의 범위를 벗어나는 칸이 있으면 이동 X
tempMovedShark[k].X = nx;
tempMovedShark[k].Y = ny;
moveSharkDFS(nx, ny, k + 1);
}
}
void moveShark() {
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++) {
if (shark[i][j]) {
moveSharkDFS(i, j, 0);
shark[i][j] = false;
}
}
}
for (int i = 0; i < 3; i++) {
if (fish[movedShark[i].X][movedShark[i].Y].size()) { // 상어가 이동한 칸에 물고기가 있으면
fish[movedShark[i].X][movedShark[i].Y] = {}; // 그 칸에 있는 모든 물고기를 제외시키고
smell[movedShark[i].X][movedShark[i].Y] = t; // 물고기 냄새를 남긴다.
}
if (i == 2) shark[movedShark[i].X][movedShark[i].Y] = true; // 상어의 최종 위치
}
}
4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
상어가 (i, j)에 냄새를 남길 때 smell[i][j]의 배열에 현재까지 진행한 연습 횟수를 값으로 저장했습니다.
따라서 if(현재까지 진행한 연습 횟수 - smell[i][j] == 2) 일 때 제거해 주면 됩니다.
int t = 0; // 현재까지 진행한 연습 횟수
int smell[5][5]; //몇 번째 연습 때 생성된 냄새인지 저장
// 4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
void removeSmell() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (t - smell[i][j] == 2) {
smell[i][j] = 0;
}
}
}
}
5. 1에서 사용한 복제 마법이 완료된다.
1번에서 백업해 두었던 물고기를 복제해 줍니다.
vector<int> fish[5][5];
vector<int> clonedFish[5][5]; // 물고기 복제 후
//5. 1에서 사용한 복제 마법이 완료된다.
void cloneFish() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (auto dir : clonedFish[i][j]) {
fish[i][j].push_back(dir);
}
}
}
}
6. 1~5번에서 구현한 함수로 연습을 진행한다.
연습마다 초기화, 현재까지 진행한 연습 횟수 카운트가 필요합니다.
물고기의 개수는 vector의 사이즈와 같습니다.
// 매 연습마다 초기화
void init() {
maxFishCnt = -1;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
movedFish[i][j] = {};
clonedFish[i][j] = {};
}
}
for (int i = 0; i < 3; i++) {
tempMovedShark[i] = {};
movedShark[i] = {};
}
}
// 물고기 개수 리턴
int getFishCnt() {
int cnt = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cnt += fish[i][j].size();
}
}
return cnt;
}
int solve() {
input();
while (s--) {
t++; //현재까지 진행한 연습 횟수 1증가
init();
backupFish(); // 1
moveFish(); // 2
moveShark(); // 3
removeSmell(); // 4
cloneFish(); // 5
}
return getFishCnt();
}
<전체 C++소스코드>
|
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
|
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
#define N 4
#define X first
#define Y second
const int fishDx[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1}; // 물고기 방향 1 ~ 8
const int fishDy[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
const int sharkDx[5] = {0, -1, 0, 1, 0}; // 상어 방향 1 ~ 4
const int sharkDy[5] = {0, 0, -1, 0, 1};
vector<int> fish[5][5];
vector<int> clonedFish[5][5]; // 물고기 복제 후
vector<int> movedFish[5][5]; // 물고기 이동 후
pair<int, int> tempMovedShark[3];
pair<int, int> movedShark[3]; // 상어가 이동한 좌표
int maxFishCnt = -1;
bool shark[5][5];
int smell[5][5]; //몇 번째 연습 때 생성된 냄새인지 저장
int m, s;
int t = 0; // 현재까지 진행한 연습 횟수
// 매 연습마다 초기화
void init() {
maxFishCnt = -1;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
movedFish[i][j] = {};
clonedFish[i][j] = {};
}
}
for (int i = 0; i < 3; i++) {
tempMovedShark[i] = {};
movedShark[i] = {};
}
}
//1. 모든 물고기를 복제한다. 5번에서 실제 복제가 된다.
void backupFish() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
clonedFish[i][j] = fish[i][j];
}
}
}
//2. 모든 물고기가 한 칸 이동한다.
void moveFish() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (auto dir : fish[i][j]) {
int cnt = 8; // 최대 7번까지 반시계 방향으로 회전해볼 수 있다.
bool moved = false;
int tempDir = dir;
while (cnt--) {
int nx = i + fishDx[tempDir];
int ny = j + fishDy[tempDir];
// 격자 범위를 벗어나는 칸, 상어가 있는 칸, 물고기의 냄새가 있는 칸이면 이동할 수 없다.
if (nx < 1 || ny < 1 || nx> N || ny > N || shark[nx][ny] || smell[nx][ny]) {
tempDir--; //반시계 방향으로 회전
if (tempDir == 0) tempDir = 8;
continue;
}
// 그 외의 경우에는 그 칸으로 이동한다.
moved = true;
movedFish[nx][ny].push_back(tempDir);
break;
}
if (!moved) movedFish[i][j].push_back(dir); //이동할 수 있는 칸이 없으면 이동 X
}
}
}
// 물고기들의 이동 정보를 실제로 반영
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
fish[i][j] = movedFish[i][j];
}
}
}
// 3. 상어가 연속해서 3칸 이동한다.
void moveSharkDFS(int x, int y, int k) {
if (k == 3) { // 상어가 3칸 이동
int fishCnt = 0;
bool visited[5][5]; //상어가 이미 먹은 물고기를 중복해서 먹지 않도록 방문 체크
fill(&visited[0][0], &visited[4][5], false);
for (int i = 0; i < k; i++) {
auto cur = tempMovedShark[i];
if (!visited[cur.X][cur.Y]) {
fishCnt += fish[cur.X][cur.Y].size();
visited[cur.X][cur.Y] = true;
}
}
// 중복 순열 DFS는 사전순으로 먼저 찾기 때문에 각 경우의수에서 물고기가 더 많아졌는지만 판단하면 된다.
if (fishCnt > maxFishCnt) {
maxFishCnt = fishCnt;
for (int i = 0; i < k; i++) {
movedShark[i] = tempMovedShark[i];
}
}
return;
}
for (int dir = 1; dir <= 4; dir++) {
int nx = x + sharkDx[dir];
int ny = y + sharkDy[dir];
if (nx < 1 || ny < 1 || nx > N || ny > N) continue; //격자의 범위를 벗어나는 칸이 있으면 이동 X
tempMovedShark[k].X = nx;
tempMovedShark[k].Y = ny;
moveSharkDFS(nx, ny, k + 1);
}
}
void moveShark() {
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++) {
if (shark[i][j]) {
moveSharkDFS(i, j, 0);
shark[i][j] = false;
}
}
}
for (int i = 0; i < 3; i++) {
if (fish[movedShark[i].X][movedShark[i].Y].size()) { // 상어가 이동한 칸에 물고기가 있으면
fish[movedShark[i].X][movedShark[i].Y] = {}; // 그 칸에 있는 모든 물고기를 제외시키고
smell[movedShark[i].X][movedShark[i].Y] = t; // 물고기 냄새를 남긴다.
}
if (i == 2) shark[movedShark[i].X][movedShark[i].Y] = true; // 상어의 최종 위치
}
}
// 4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
void removeSmell() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (t - smell[i][j] == 2) {
smell[i][j] = 0;
}
}
}
}
//5. 1에서 사용한 복제 마법이 완료된다.
void cloneFish() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (auto dir : clonedFish[i][j]) {
fish[i][j].push_back(dir);
}
}
}
}
// 물고기 개수 리턴
int getFishCnt() {
int cnt = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cnt += fish[i][j].size();
}
}
return cnt;
}
void input() {
cin >> m >> s;
for (int i = 0; i < m; i++) {
int fx, fy, d; cin >> fx >> fy >> d;
fish[fx][fy].push_back(d);
}
int sx, sy; cin >> sx >> sy;
shark[sx][sy] = true;
}
int solve() {
input();
while (s--) {
t++; //현재까지 진행한 연습 횟수 1증가
init();
backupFish(); // 1
moveFish(); // 2
moveShark(); // 3
removeSmell(); // 4
cloneFish(); // 5
}
return getFishCnt();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cout << solve();
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 1938번] 통나무 옮기기 (0) | 2023.04.04 |
|---|---|
| [백준 9944번] NxM 보드 완주하기 (0) | 2023.04.01 |
| [백준 17135번] 캐슬 디펜스 (0) | 2023.03.28 |
| [백준 9205번] 맥주 마시면서 걸어가기 (0) | 2023.03.27 |
| [백준 1743번] 음식물 피하기 (0) | 2023.03.26 |