https://www.acmicpc.net/problem/23291
23291번: 어항 정리
마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바
www.acmicpc.net
풀이
더보기
우선 NxN 형태의 2차원 벡터를 이용하여 어항의 배치를 표현하였으며, 어항이 존재하지 않는 좌표는 -1로 표현하였다.
그리고 문제에서는 어항이 위로 쌓이게 되지만 편의상 배열의 아래로 쌓이도록 표현하였다.
따라서 위 그림을 배열로 표현하면 다음과 같다. 코드 상에서는 board라는 변수를 사용한다.
|
1
2
3
4
5
6
7
8
|
-1 -1 3 14 9 3 11 8
-1 -1 3 5 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
|
cs |
1. 시작/종료 조건
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
bool if_end() {
// 물고기 수에 따라 종료조건이 성립한 경우 true 반환
int max_fishes = *max_element(board[0].begin(), board[0].end());
int min_fishes = *min_element(board[0].begin(), board[0].end());
return ((max_fishes - min_fishes) <= K);
}
....
int solve() {
int count = 0;
while (!if_end()) {
// if_end()에서 false를 반환한 경우 count를 1 증가시키고, 어항을 정리(move() 함수)
count++;
move();
}
// if_end()에서 true를 반환한 경우 count 반환
return count;
}
|
cs |
- if_end() 함수에서 max_element() 와 min_element() 함수를 이용하여 최대, 최소 물고기 수를 계산하였으며, 두 수의 차가 K 이하인 경우 true를 반환하여 알고리즘이 종료되도록 구성하였다.
- solve() 함수에서는 if_end()가 true를 반환할 때 까지 카운트를 세며, 어항을 정리하는 move() 함수를 호출한다.
2. 어항 정리
우선은 어항 정리를 두 번하게 되는데, 어항 정리를 할 때마다 물고기를 이동시킨다. 이 때 물고기를 이동시키는 함수 move_fishes()는 다음과 같다.
|
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
|
// 물고기 이동 함수
void move_fishes() {
vector<vector<int>> new_board = board;
// 물고기가 없는(-1)인 좌표를 제외한 모든 좌표에 대해 인근 좌표와 오차 계산
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
if (board[y][x] == -1) continue;
for (int d = 0; d < 4; ++d) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N || board[ny][nx] == -1)
continue;
// 각 좌표에 대하여 (인근 좌표와의 차/5) 만큼 빼서 new_board에 기록
new_board[y][x] += (int) (board[ny][nx] - board[y][x]) / 5;
}
}
}
// 물고기 이동 후 다시 board를 일자로 펴줌 (flat_bowl 벡터에 왼쪽열 부터 중심에 가까운 순서대로 push)
vector<int> flat_bowl;
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
if (new_board[y][x] == -1)
continue;
else
flat_bowl.push_back(new_board[y][x]);
}
}
//board를 초기화 한 후 board[0]를 flat_bowl로 교체
board = vector<vector<int>>(N, vector<int>(N, -1));
board[0] = flat_bowl; // board[0]를 flat_bowlf로 교체
}
|
cs |
- 인근 좌표에 대하여 물고기가 이동하는데, 이 때 물고기 이동은 모든 칸에 대하여 동시에 발생한다. 따라서 구현할 때 new_board라는 새로운 변수를 할당하고, board의 각 좌표에 대하여 인근 좌표와 계산한 뒤 new_board의 값을 갱신하였다. 따라서, 모든 인접한 칸에 대하여 동시에 물고기가 이동한 것과 같은 결과가 new_board에 저장된다.(board의 값은 변경없으므로)
|
1
|
new_board[y][x] += (int) (board[ny][nx] - board[y][x]) / 5;
|
cs |
- 각 좌표에 대하여 (board[ny][nx] - board[y][x])/5 는 비교 대상(board[ny][nx])에 대하여 주거나 받는 물고기 수를 의미하게 된다. 위의 계산을 -1이 아닌 모든 좌표에 대하여 수행하게되면 물고기가 이동한 것과 같이 된다.
- 또한 물고기가 모두 이동한 경우 다시 어항을 일렬로 놓아야 한다. 이 때 flat_bowl 벡터를 생성하여 (배열상)왼쪽위의 어항부터 오른쪽 아래의 어항까지 차례로 push한다. 그리고 board를 초기화 한 후 board의 첫 번째 행을 flat_bowl로 교체하면 어항이 일렬로 놓이게 된다.
어항이 이동하는 함수 move()는 다음과 같다.
|
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
|
void move() {
int ly = 1, lx = 1; // length y, length x
int sx = 0; //start x
// 1. 물고기 추가
int min_fishes = *min_element(board[0].begin(), board[0].end());
for (int i = 0; i < N; ++i) {
if (board[0][i] == min_fishes)
board[0][i]++;
}
// 2. 어항을 말며 움직이기
while (sx + ly + lx <= N) {
for (int y = 0; y < ly; ++y) {
for (int x = 0; x < lx; ++x) {
int ny = lx - x;
int nx = sx + lx + y;
board[ny][nx] = board[y][x + sx];
board[y][x + sx] = -1;
}
}
sx += lx;
if (ly == lx) ly++;
else lx++;
pboard();
}
// 3. 물고기 이동
move_fishes();
// 4. 중심을 기준으로 어항 2번 이동
sx = 0;
ly = 1;
lx = N / 2;
for (int i = 0; i < 2; ++i) {
for (int y = 0; y < ly; ++y) {
for (int x = 0; x < lx; ++x) {
int ny = 2 * ly - y - 1;
int nx = 2 * lx + sx - x - 1;
board[ny][nx] = board[y][x + sx];
board[y][x + sx] = -1;
}
}
sx += lx;
lx /= 2;
ly *= 2;
}
// 5. 물고기 이동
move_fishes();
|
cs |
- 물고기 추가
- board의 첫 번째 행에서 최솟값을 찾은 후 board의 첫 번째 행에서 이 값과 같은 값이 있는 경우 1을 더해주었다.
- 어항 정리1
- sx는 움직일 어항의 시작 좌표, ly는 움직일 어항의 세로 길이, lx는 움직일 어항의 가로 길이를 뜻한다.
12345678-1 -1 3 14 9 3 11 8-1 -1 3 5 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1cs - 위의 값을 이용하여 sx+ly+lx의 값이 N보다 크게 되는 경우에 어항이 이동을 멈춘다.
(어항이 움직이고 나서 기준행을 제외하고 가장 오른쪽의 좌표는 sx에 대하여 ly, lx를 더한 값-1과 같기 때문, 이 값이 N보다 크다는 것은 어항이 이동할 경우 2차원 배열의 크기를 넘는다는 뜻 )
12345678910111213while (sx + ly + lx <= N) {for (int y = 0; y < ly; ++y) {for (int x = 0; x < lx; ++x) {int ny = lx - x;int nx = sx + lx + y;board[ny][nx] = board[y][x + sx];board[y][x + sx] = -1;}}sx += lx;if (ly == lx) ly++;else lx++;}cs - 배열이 이동할 위치의 좌표 ny, nx를 계산(배열의 90도 회전)하고, board의 값을 바꿔준다.
(이 변환하는 코드가 이해가 되지 않는다면 배열 회전 알고리즘을 좀 더 공부하는 것을 추천) - 그리고 시작 좌표에 lx를 더하여 시작 좌표를 갱신하고 ly, lx 값 역시 갱신해준다.
(예시를 살펴보면 회전시킬 배열의 ly, lx가 ly를 시작으로 한번 돌아갈 때 마다 번갈아가며 1씩 증가하는 것을 알 수 있다.)
빨간색 네모가 다음 턴에 회전할 배열
- 기본 입력에 대하여 배열의 상태를 출력하면 다음과 같다.
123456789101112131415161718192021222324252627288 75 2 3 14 9 2 11 8-1 3 3 14 9 3 11 8-1 5 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 3 14 9 3 11 8-1 -1 3 5 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 9 3 11 8-1 -1 -1 -1 14 5 -1 -1-1 -1 -1 -1 3 3 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1cs
- 기본 입력에 대하여 배열의 상태를 출력하면 다음과 같다.
- sx는 움직일 어항의 시작 좌표, ly는 움직일 어항의 세로 길이, lx는 움직일 어항의 가로 길이를 뜻한다.
- 물고기 이동
- move_fishes()를 이용하여 물고기를 이동시키고 어항을 다시 일렬로 세운다.
- 어항 정리2
- 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 시계방향을 180도 회전 후 N/2개에 놓는 작업을 2번 반복한다.
12345678910111213141516sx = 0;ly = 1;lx = N / 2;for (int i = 0; i < 2; ++i) {for (int y = 0; y < ly; ++y) {for (int x = 0; x < lx; ++x) {int ny = 2 * ly - y - 1;int nx = 2 * lx + sx - x - 1;board[ny][nx] = board[y][x + sx];board[y][x + sx] = -1;}}sx += lx;lx /= 2;ly *= 2;}cs - sx = 0, ly = 1, lx = N/2(0~배열의 중심)로 초기화한다.
- 위에서 어항이 이동하는 것과 비슷하게 이동할 배열에 대해서 ny, nx 값을 계산하고 좌표를 또한 바꿔준다.
이번에는 시계방향으로 180도 회전하므로 ny, nx 계산식이 조금 다르게된다. - sx에 lx를 더하여 시작 좌표를 갱신하고, lx는 2로 나누어 주고, ly는 2를 곱해준다.
빨간색은 이동할 배열 - 기본 입력의 경우 위의 이동에 대한 배열의 상태를 출력하면 다음과 같다.
12345678910111213141516171819202122232425269 10 5 5 6 3 10 8-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 6 3 10 8-1 -1 -1 -1 5 5 10 9-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 10 8-1 -1 -1 -1 -1 -1 10 9-1 -1 -1 -1 -1 -1 5 5-1 -1 -1 -1 -1 -1 3 6-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 -1cs
- 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 시계방향을 180도 회전 후 N/2개에 놓는 작업을 2번 반복한다.
- 물고기 이동
- 어항을 정리했으므로 move_fishes()를 이용하여 물고기를 또 이동시킨다.
위의 move()함수를 if_end()가 true를 반환할 때까지 반복하며 count를 더해준다.
전체 코드
더보기
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dy[] = {0, 1, 0, -1};
int dx[] = {1, 0, -1, 0};
int N, K;
vector<vector<int>> board;
bool if_end() {
// 물고기 수에 따라 종료조건이 성립한 경우 true 반환
int max_fishes = *max_element(board[0].begin(), board[0].end());
int min_fishes = *min_element(board[0].begin(), board[0].end());
return ((max_fishes - min_fishes) <= K);
}
// 물고기 이동 함수
void move_fishes() {
vector<vector<int>> new_board = board;
for (int y = 0; y < N; ++y) {
for (int x = 0; x < N; ++x) {
if (board[y][x] == -1) continue;
for (int d = 0; d < 4; ++d) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N || board[ny][nx] == -1)
continue;
// 각 좌표에 대하여 (인근 좌표와의 차/5) 만큼 빼서 new_board에 기록
// -> 모든 인접칸에 대하여 동시에 발생한 것과 같게됨
new_board[y][x] += (int) (board[ny][nx] - board[y][x]) / 5;
}
}
}
// 물고기 이동 후 다시 board를 일자로 펴줌 (flat_bowl 벡터에 왼쪽열 부터 중심에 가까운 순서대로 push)
vector<int> flat_bowl;
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
if (new_board[y][x] == -1)
continue;
else
flat_bowl.push_back(new_board[y][x]);
}
}
//board를 초기화 한 후 board[0]를 flat_bowl로 교체
board = vector<vector<int>>(N, vector<int>(N, -1));
board[0] = flat_bowl; // board[0]를 flat_bowlf로 교ㅊ[
}
void move() {
int ly = 1, lx = 1; // length y, length x
int sx = 0; // start y, start x
// 1. 물고기 추가
int min_fishes = *min_element(board[0].begin(), board[0].end());
for (int i = 0; i < N; ++i) {
if (board[0][i] == min_fishes)
board[0][i]++;
}
// 2. 어항을 말며 움직이기
while (sx + ly + lx <= N) {
for (int y = 0; y < ly; ++y) {
for (int x = 0; x < lx; ++x) {
int ny = lx - x;
int nx = sx + lx + y;
board[ny][nx] = board[y][x + sx];
board[y][x + sx] = -1;
}
}
sx += lx;
if (ly == lx) ly++;
else lx++;
}
// 3. 물고기 이동
move_fishes();
// 4. 중심을 기준으로 어항 2번 이동
sx = 0;
ly = 1;
lx = N / 2;
for (int i = 0; i < 2; ++i) {
for (int y = 0; y < ly; ++y) {
for (int x = 0; x < lx; ++x) {
int ny = 2 * ly - y - 1;
int nx = 2 * lx + sx - x - 1;
board[ny][nx] = board[y][x + sx];
board[y][x + sx] = -1;
}
}
sx += lx;
lx /= 2;
ly *= 2;
}
// 5. 물고기 이동
move_fishes();
}
int solve() {
int count = 0;
while (!if_end()) {
count++;
move();
}
return count;
}
int main() {
cin >> N >> K;
board = vector<vector<int>>(N, vector<int>(N, -1));
for (int i = 0; i < N; ++i) {
cin >> board[0][i];
}
cout << solve();
}
|
cs |
'About > Algorithm' 카테고리의 다른 글
| [백준 1202] 보석 도둑(C++ 풀이) (0) | 2022.01.03 |
|---|---|
| [백준 4256] 트리 (C++ 풀이) (0) | 2021.12.27 |
| [백준 2638번] 치즈 (C++ 풀이) (0) | 2021.12.17 |
| [알고스팟] 시계 맞추기(C++) (0) | 2021.12.14 |
| [백준 16234번] 인구이동(C++) 풀이 (0) | 2021.12.13 |
