문제
https://www.acmicpc.net/problem/2573
지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.
그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보
빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.
그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.
그림 2
그림 3
한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
입력
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
출력
첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.
예제 입력 1
5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0
예제 출력 1
2
접근
인접해 있는 네 변 중에서 물과 맞닿아 있는 변의 개수에 따라 빙산이 녹는다는 개념이 예전에 풀었던 2638 치즈랑 비슷한 문제였다. 치즈 문제는 외부 공간 내부 공간 이런 것도 따져야 했는데 얘는 숫자가 0이 되면 무조건 녹는 거라 치즈 문제보단 쉬웠다.
한 해동안 녹아야 할 빙산들이 모두 녹은 후에 다음 해로 넘어가야 하기 때문에 bfs를 사용해 각 시간(년)별 빙산의 현황을 완전 탐색을 했다.
치즈 문제에서와 마찬가지로 빙산이 0이 되어 없어졌더라도 바로 없애버리면 인접한 다른 빙산들의 결과가 영향을 받기 때문에 0이 된 빙산의 위치 정보는 일단 따로 저장해 뒀다가 하나의 너비(년)에 대한 탐색이 끝나면 그때 0으로 만들어주면 된다.
빙산이 분리됐는지 여부를 어떻게 판단할지에 대한 효율적인 방법이 처음에 한 번에 안 떠올랐다.. 처음엔 1년이 지날 때마다 빙산의 덩어리의 수를 모두 구해서 2 이상인지 확인해야 될 거라고 생각했다.
그런데 빙산의 덩어리 수를 모두 구하려면 현재 큐 안에 있는 모든 빙산들을 하나씩 꺼내서 순회를 해야 하는데 그러려고 큐에 있던 걸 꺼냈다가 다시 넣었다가 하는 게 맞나...? 싶었다. 너무 번거로울 것 같아서 처음에는 그냥 N*M 배열 전체를 순회하는 식으로 접근을 했다. (요즘에는 실전에서처럼 최대한 빠르게 접근해서 일단 문제를 해결하고 보려고 한다.) 어차피 맨 처음에 N*M 배열의 값을 입력받는데부터도 O(N * M)의 시간 복잡도가 나오기 때문에 이거 때문에 시간 초과가 날 일은 없으니.
일단 그렇게 풀어서 문제를 맞힌 다음에 다시 생각해보니까 굳이 빙산의 덩어리 수를 모두 구할 필요가 없었다. 그냥 현재 큐의 맨 앞에 있는 빙산부터 시작해서 인접한 빙산들을 모두 탐색하면 그게 한 덩어리인데, 그 한 덩어리 안에 현재까지 남아 있는 모든 빙산들이 존재하지 않는다면 빙산이 최소 두 덩어리 이상으로 쪼개졌다는 뜻이 되기 때문이다.
즉, 어느 한 덩어리 안에 있는 빙산의 개수와 현재 남아 있는 전체 빙산의 개수를 비교해서 같지 않으면 탐색을 종료하면 되는 거였다.
이렇게 코드를 변경하니 실행 시간이 130ms 이상 줄어들었다.
구현
import java.io.*;
import java.util.*;
class Main {
static int N;
static int M;
static int[][] arr;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
Queue<Iceberg> q = new LinkedList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] > 0) {
q.offer(new Iceberg(i, j, 0));
}
}
}
System.out.println(bfs(q));
}
private static int bfs(Queue<Iceberg> q) {
int currYear = 0;
List<Iceberg> willBeMelted = new ArrayList<>();
while (!q.isEmpty()) {
Iceberg currIceberg = q.poll();
// 한 너비(년)에 대한 탐색이 끝난 경우
if (currIceberg.year > currYear) {
// 현재 년에 녹은 빙산들을 0으로 만들기
for (int idx = willBeMelted.size() - 1; idx >= 0 && currYear == willBeMelted.get(idx).year; idx--) {
arr[willBeMelted.get(idx).row][willBeMelted.get(idx).col] = 0;
}
// 한 덩어리 안에 전체 빙산이 모두 들어있지 않으면 여러 덩어리로 쪼개졌다는 뜻
// 연도 출력하고 종료
if (findChunks(currIceberg) != q.size() + 1) {
return currIceberg.year;
}
currYear = currIceberg.year;
}
int meltingCnt = melt(currIceberg);
if (meltingCnt >= arr[currIceberg.row][currIceberg.col]) {
// 빙산이 완전히 녹았다면 바로 0으로 만드는 대신 해당 빙산의 위치 정보를 임시 저장
willBeMelted.add(currIceberg);
} else {
// 빙산이 남아 있다면 녹은 만큼 값 갱신하고 큐에 다시 넣기
arr[currIceberg.row][currIceberg.col] -= meltingCnt;
++currIceberg.year;
q.offer(currIceberg);
}
}
return 0;
}
// 어느 한 덩어리 안에 있는 빙산들의 개수 구하기
private static int findChunks(Iceberg start) {
boolean[][] isVisited = new boolean[N][M];
Queue<int[]> q2 = new LinkedList<>();
q2.offer(new int[] {start.row, start.col});
isVisited[start.row][start.col] = true;
int fractions = 1;
while (!q2.isEmpty()) {
int[] currLoc = q2.poll();
for (int k = 0; k < 4; k++) {
int nextRow = currLoc[0] + dx[k];
int nextCol = currLoc[1] + dy[k];
if (nextRow >= 0 && nextRow < N && nextCol >= 0 && nextCol < M && arr[nextRow][nextCol] > 0 && !isVisited[nextRow][nextCol]) {
fractions++;
isVisited[nextRow][nextCol] = true;
q2.offer(new int[] {nextRow, nextCol});
}
}
}
return fractions;
}
// 빙산의 높이가 얼만큼 줄어들어야 하는지?
private static int melt(Iceberg currIceberg) {
int meltingCnt = 0;
for (int i = 0; i < 4; i++) {
if (meltingCnt >= arr[currIceberg.row][currIceberg.col]) {
break;
}
int nextRow = currIceberg.row + dx[i];
int nextCol = currIceberg.col + dy[i];
if (nextRow >= 0 && nextRow < N && nextCol >= 0 && nextCol < M) {
if (arr[nextRow][nextCol] == 0) {
meltingCnt++;
}
}
}
return meltingCnt;
}
static class Iceberg {
int row;
int col;
int year;
Iceberg(int row, int col, int year) {
this.row = row;
this.col = col;
this.year = year;
}
}
}백준 문제 너무 오랜만에 올린다... 반성합니다..
