Baekjoon 2573 빙산
문제 이해
2차원 평면에 해수면과 빙하가 주어진다.
물에 닿은 빙하는 1년에 1씩 녹는데, 물에 닿은 표면(상하좌우)이 많을 수록 더 빨리 녹는다.
해수면은 0, 빙하의 높이가 정수로 주어질 때 몇 년 후에 빙하가 2개 이상으로 쪼개지는지 구하는 문제이다.
입출력 조건 확인
입출력 조건을 보고 문제를 봤을 때 시간이 아슬아슬해 보였다.
내가 생각한 풀이는 빙하가 녹는 이벤트에서 한 번, 빙하가 두 개로 쪼개졌는지 한 번 전체 맵을 순회해야 하는데, 앞선 2개의 깊이 우선 탐색 문제를 풀었던 경험으로 보자면 시간이 아슬아슬했다.
고민을 길게 하다가 다른 방법이 생각이 나지 않아서 일단 박치기를 해보기로 했다.
문제 풀이 내용 정리
맵 그리기
beforeMap과 afterMap 두 개를 그렸다.
첫 번째 이유는 빙산이 두 개 이상으로 갈라진 것을 확인하기 위해서는 깊이 우선 탐색을 해야 하고, 탐색을 시작하면 다녀갔다는 표시를 하면서 탐색을 해야 하는데 빙산의 높이가 좌표에 저장되어 있어서 불가능했기 때문이고, 두 번째 이유는 한 칸의 빙하가 완전히 녹아버린 것이 같은 기준 시간 안에서 다른 빙하에게 영향을 주면 안됐기 때문이다.
afterMap은 빙산이 갈라졌는지 확인하는 용도로 사용했고, beforeMap은 빙산을 녹이는 과정에서 사용했다.빙산 녹이기
warming 메소드가 빙산을 녹이는 메소드이다.
개개의 좌표를 전부 돌면서 빙하가 맞는지, 빙하가 맞다면 상하좌우 중 몇 칸이 물에 닿아 있는지를 구해서 물에 닿아 있는 면적 만큼 빙하의 높이를 차감했다.빙산 쪼개짐 확인
빙산이 쪼개지면 답이 구해진 것이므로 매 년 빙산이 쪼개졌는지 확인하기 위해 iceAge 메소드를 돌렸다.
전체 맵을 순회하면서 빙산을 만나면 인접한 빙산을 모두 -1로 만든다. 이후에 다시 한 번 탐색하지 않은 빙하를 만난다면 빙하의 수(island)를 늘린다.시간의 흐름
반복문으로 반복해서 매년 빙산을 녹이고 쪼개짐을 확인했다.
빙산이 전부 녹았거나 두 개 이상으로 쪼개지면 반복문을 종료하고 종료한 원인에 따른 결과를 출력한다.
Java
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
import java.util.Scanner;
public class Main {
static byte[][] beforeMap;
static byte[][] afterMap;
static byte[] dX = {1, -1, 0, 0};
static byte[] dY = {0, 0, 1, -1};
static int sizeX;
static int sizeY;
static int island = 0;
static int depth = 0;
static int year = 0;
static boolean noIce = false;
public static void warming() {
for (int x = 0; x < sizeX; x++) {
for (int y = 0; y < sizeY; y++) {
if (beforeMap[x][y] > 0) {
int hot = 0;
for (int i = 0; i < 4; i++) {
int newX = x + dX[i];
int newY = y + dY[i];
if (newX < 0 | newX >= sizeX | newY < 0 | newY >= sizeY)
continue;
if (beforeMap[newX][newY] == 0)
hot++;
}
afterMap[x][y] -= hot;
if (afterMap[x][y] < 0) afterMap[x][y] = 0;
}
}
}
for (int i = 0; i < sizeX; i++) {
beforeMap[i] = afterMap[i].clone();
}
}
public static void iceAge(int x, int y) {
if (afterMap[x][y] > 0) {
if (depth == 0) island += 1;
afterMap[x][y] = -1;
for (int i = 0; i < 4; i++) {
int newX = x + dX[i];
int newY = y + dY[i];
if (newX < 0 | newX >= sizeX | newY < 0 | newY >= sizeY)
continue;
if (afterMap[newX][newY] > 0) {
depth += 1;
iceAge(newX, newY);
depth -= 1;
}
}
}
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
String[] mapSize = sc.nextLine().split(" ");
sizeX = Integer.parseInt(mapSize[0]);
sizeY = Integer.parseInt(mapSize[1]);
beforeMap = new byte[sizeX][sizeY];
afterMap = new byte[sizeX][sizeY];
for (int i = 0; i < sizeX; i++) {
String[] tmp = sc.nextLine().split(" ");
for (int j = 0; j < tmp.length; j++) {
beforeMap[i][j] = (byte) Integer.parseInt(tmp[j]);
}
}
for (int i = 0; i < sizeX; i++) {
afterMap[i] = beforeMap[i].clone();
}
while(!noIce) {
year += 1;
warming();
for (int i = 0; i < sizeX; i++) {
for (int j = 0; j < sizeY; j++) {
iceAge(i, j);
}
}
for (int i = 0; i < sizeX; i++) {
afterMap[i] = beforeMap[i].clone();
}
if (island == 0) noIce = true;
else if (island > 1) break;
island = 0;
}
System.out.println(noIce ? 0 : year);
}
}
코드 문제점 및 해결 방법
첫 성공 때 메모리가 거의 200MB에 달했다.
제한에 거의 가까워져서 이 방법이 아닌가 생각했는데 큰 범위를 할당하는 Map들을 byte로 변경하니 70MB 수준으로 크게 줄어들었다.
다음에 더 큰 2차원 이상의 배열이 나오면 메모리 제한을 생각해서 자료형을 결정하면 좋을 것 같다.
전역 변수도 산처럼 쌓였고, 메소드도 들여쓰기가 산처럼 쌓였다.
아무리 생각해도 구현 미숙인 것 같아서 나중에 다시 보고 고칠 수 있으면 좋을 것 같다.