백준(BOJ) 삼성 SW 역량 테스트 기출 문제 문제집: 어항 정리(골드 1)
문제 출처: https://www.acmicpc.net/problem/23291
23291번: 어항 정리
마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바
www.acmicpc.net
1.알고리즘
어항을 돌리고 올리는 과정이 힘들었다... 좌표에 약하다는 건 알고 있었는데, 조금 복잡해지니까 계산을 하다가도 왜 계산을 하고 있는 지 잊고 난리가 났었다ㅠ 어찌저찌 좌표 계산해서 진행했는데, 좌표 관련된 문제들 더 봐야할 것같다.
- 구현 / 브루트포스
- 정수형 이차원 배열로 어항 표현
- (물고기 현황 체크 > 새 물고기 추가 > 공중부양&회전 > 물고기 수 조절 > 한 줄로 어항 정렬 > 공중 부양 > 물고기 수 조절 > 한 줄로 어항 정렬) 반복
123456789101112int time = 0;while(checkFishNum()) {putNewFish();levitateNRotate();controlFish();lineUp();levitate();controlFish();lineUp();time++;}
cs
- 물고기 현황 체크
- 어항 최대 물고기 개수, 최소 물고기 개수 카운팅 후 비교. K이하면 false, 초과면 true로 반복 여부 갱신
1234567891011121314private static boolean checkFishNum() {int maxFishNum = 0;int minFishNum = Integer.MAX_VALUE;for(int i=0; i<N; i++) {int fishNum = fishbowl[N-1][i];maxFishNum = Math.max(fishNum, maxFishNum);minFishNum = Math.min(fishNum, minFishNum);}minNum = minFishNum;int fishNumDiffer = maxFishNum-minFishNum;if(fishNumDiffer<=K) return false;return true;}
cs
- 어항 최대 물고기 개수, 최소 물고기 개수 카운팅 후 비교. K이하면 false, 초과면 true로 반복 여부 갱신
- 새 물고기 추가
- 위에서 카운팅한 최소 물고기 개수를 참고. 어항을 탐색하며 최소 물고기 개수 일치 시 +1
1234567private static void putNewFish() {for(int i=0; i<N; i++) {if(fishbowl[N-1][i]==minNum) {fishbowl[N-1][i]++;}}}
cs
- 위에서 카운팅한 최소 물고기 개수를 참고. 어항을 탐색하며 최소 물고기 개수 일치 시 +1
- 공중부양&회전
- step 회전 단계, col 현재 열, w 너비, h 높이, nw 다음 너비, nh 다음 높이
- 다음 높이*다음 넓이가 N보다 작거나 같은 경우까지만 반복
- (N-1, col)~(N-1-h, col+w)까지 반복
- nr = (N-1-w)+(c-col)
- w는 이전 너비 == 이번 높이 >>N-1-w는 시작 행
- c=col+x, (x<w, 이전 열 위치 == 현재 행 위치)
- c-col = col+x-col > x >> 현재 행 위치
- nc = (col+w)+(N-1-r)
- w는 이전 너비 > col(현재 열)+너비(추가로 뒤로 가야하는 너비) >> 시작 열
- N-1-r = N-1-(N-1-y), (y<h, 이전 행 위치 == 현재 열 위치)
- N-1-N+1+y = y >> 현재 열 위치
1234567891011121314151617181920212223242526private static void levitateNRotate() {int step = 0, col = 0;int w = 1, nw = 1;int h = 1, nh = 2;while(nw*nh<=N) {for(int r=N-1; r>N-1-h; r--) {for(int c=col; c<col+w; c++) {int nr = (N-1-w)+(c-col);int nc = (col+w)+(N-1-r);fishbowl[nr][nc] = fishbowl[r][c];fishbowl[r][c] = 0;}}if(step%2==0) {h++;nw++;}else {w++;nh++;}step++;col+=((step-1)/2+1);}}cs - 물고기 개체 조절
- (N-1, N-1)~(0, 0)까지 반복
- 현재 어항 물고기 수를 newFishbowl에 추가
- 인접한 4방향 탐색하며 개체 수 조절
123456789101112131415161718192021222324252627private static void controlFish() {int[][] newFishbowl = new int[N][N];for(int r=N-1; r>=0; r--) {for(int c=N-1; c>=0; c--) {if(fishbowl[r][c]==0) continue;newFishbowl[r][c]+=fishbowl[r][c];for(int d=0; d<4; d++) {int nr = r+dx[d];int nc = c+dy[d];if(nr<0 || nr>=N || nc<0 || nc>=N) continue;if(fishbowl[nr][nc]==0) continue;if(fishbowl[r][c] <= fishbowl[nr][nc]) continue;int differ = fishbowl[r][c]-fishbowl[nr][nc];int quotient = differ/5;if(quotient<=0) continue;newFishbowl[r][c]-=quotient;newFishbowl[nr][nc]+=quotient;}}}fishbowl = newFishbowl;}
cs
- 한 줄 정렬
- idx로 어항 순서 설정(초기값 0)
- 열 순서대로(0~N-1) 탐색
- 어항이 없으면(==물고기가 0이면) 다음 열로 넘겨줌
- 어항이 있으면 (N-1~0)까지 행 탐색, 탐색 중 어항이 없으면 다음 열로 넘김
- 존재하는 어항 [N-1][idx]에 삽입
1234567891011121314private static void lineUp() {int idx = 0;int[] newFishbowl = new int[N];for(int c=0; c<N; c++) {if(fishbowl[N-1][c] == 0) continue;for(int r=N-1; r>=0; r--) {if(fishbowl[r][c] == 0) continue;newFishbowl[idx++] = fishbowl[r][c];fishbowl[r][c] = 0;}}fishbowl[N-1] = newFishbowl;}
cs
- 공중부양
- 반으로 나눠 180도 회전 > 앞쪽의 반을 거꾸로 뒤집어 뒷 열에 한 줄 위로 이동
- [N-1][c] >이동> [N-2][N-1-c]
- 열 카운팅을 위한 별도의 idx 설정(초기값 N-3)
- [r][c] >이동> [idx--][(N-1)-(c-step)]
- N-1-(c-step) > c-step = startC+nS-step = step+nS-step, (nS<nStep, 현재 이동할 열)
- nS >> (N-1)-nS == 마지막 줄로부터 nS번째 열
- 반으로 나눠 180도 회전 > 앞쪽의 반을 거꾸로 뒤집어 뒷 열에 한 줄 위로 이동
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
private static void levitate() {
int step = N/2;
for(int c=0; c<step; c++) {
fishbowl[N-2][N-1-c] = fishbowl[N-1][c];
fishbowl[N-1][c] = 0;
}
int startC = step;
int nStep = step/2;
for(int c=startC; c<startC+nStep; c++) {
int idx = N-3;
for(int r=N-2; r<N; r++) {
fishbowl[idx--][(N-1)-(c-step)] = fishbowl[r][c];
fishbowl[r][c] = 0;
}
}
}
|
cs |
2. 유의 사항
3. 어려웠던 점, 해결 방법
- 공중 부양 시, idx 초기값 설정을 매 열마다 해줘야함
- 매 열마다 해주지 않아도 예제는 모두 통과함 > 검사과정에서 런타임 에러 발생
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
153
154
155
156
157
158
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, K, minNum;
static int[][] fishbowl;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static class Node{
int r, c;
Node(int r, int c){
this.r = r;
this.c = c;
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
fishbowl = new int[N][N];
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
fishbowl[N-1][i] = Integer.parseInt(st.nextToken());
}
int time = 0;
while(checkFishNum()) {
putNewFish();
levitateNRotate();
controlFish();
lineUp();
levitate();
controlFish();
lineUp();
time++;
}
System.out.println(time);
}
private static void putNewFish() {
for(int i=0; i<N; i++) {
if(fishbowl[N-1][i]==minNum) {
fishbowl[N-1][i]++;
}
}
}
private static void levitateNRotate() {
int step = 0, col = 0;
int w = 1, nw = 1;
int h = 1, nh = 2;
while(nw*nh<=N) {
for(int r=N-1; r>N-1-h; r--) {
for(int c=col; c<col+w; c++) {
int nr = (N-1-w)+(c-col);
int nc = (col+w)+(N-1-r);
fishbowl[nr][nc] = fishbowl[r][c];
fishbowl[r][c] = 0;
}
}
if(step%2==0) {
h++;
nw++;
}else {
w++;
nh++;
}
step++;
col+=((step-1)/2+1);
}
}
private static void controlFish() {
int[][] newFishbowl = new int[N][N];
for(int r=N-1; r>=0; r--) {
for(int c=N-1; c>=0; c--) {
if(fishbowl[r][c]==0) continue;
newFishbowl[r][c]+=fishbowl[r][c];
for(int d=0; d<4; d++) {
int nr = r+dx[d];
int nc = c+dy[d];
if(nr<0 || nr>=N || nc<0 || nc>=N) continue;
if(fishbowl[nr][nc]==0) continue;
if(fishbowl[r][c] <= fishbowl[nr][nc]) continue;
int differ = fishbowl[r][c]-fishbowl[nr][nc];
int quotient = differ/5;
if(quotient<=0) continue;
newFishbowl[r][c]-=quotient;
newFishbowl[nr][nc]+=quotient;
}
}
}
fishbowl = newFishbowl;
}
private static void lineUp() {
int idx = 0;
int[] newFishbowl = new int[N];
for(int c=0; c<N; c++) {
if(fishbowl[N-1][c] == 0) continue;
for(int r=N-1; r>=0; r--) {
if(fishbowl[r][c] == 0) continue;
newFishbowl[idx++] = fishbowl[r][c];
fishbowl[r][c] = 0;
}
}
fishbowl[N-1] = newFishbowl;
}
private static void levitate() {
int step = N/2;
for(int c=0; c<step; c++) {
fishbowl[N-2][N-1-c] = fishbowl[N-1][c];
fishbowl[N-1][c] = 0;
}
int startC = step;
int nStep = step/2;
for(int c=startC; c<startC+nStep; c++) {
int idx = N-3;
for(int r=N-2; r<N; r++) {
fishbowl[idx--][(N-1)-(c-step)] = fishbowl[r][c];
fishbowl[r][c] = 0;
}
}
}
private static boolean checkFishNum() {
int maxFishNum = 0;
int minFishNum = Integer.MAX_VALUE;
for(int i=0; i<N; i++) {
int fishNum = fishbowl[N-1][i];
maxFishNum = Math.max(fishNum, maxFishNum);
minFishNum = Math.min(fishNum, minFishNum);
}
minNum = minFishNum;
int fishNumDiffer = maxFishNum-minFishNum;
if(fishNumDiffer<=K) return false;
return true;
}
}
|
cs |
5. 고민
- 좌표에 대한 고민이 많아졌다... 이번 문제도 좌표 계산 때문에 이틀 정도 골머리를 앓았는데, 최종적으로 나온 수식만 보면 고민했던 것에 비해서는 직관적인 것도 같다...
- 근데 더 쉽게 하는 방법은 없나..?
'Algorithms > 백준' 카테고리의 다른 글
| [백준_23290]마법사 상어와 복제 with Java (0) | 2022.01.05 |
|---|---|
| [백준_1463]1로 만들기 with Python, Java (0) | 2021.10.12 |
| [백준_16236]아기 상어 with Python, Java (0) | 2021.08.26 |
| [백준_4358]생태학 with Java (0) | 2021.08.04 |
| [백준_12904]A와 B with Python (0) | 2021.06.30 |
댓글