문제
지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.
빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다.
한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
입력
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
출력
첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.
주안점
dfs 또는 bfs를 통해 빙산을 순회하며 조건을 수행하는 문제.
조건이 2개(분리된 빙산 체크, 바다만큼 빙산 감소)이기 때문에
1번의 순회로 분리된 빙산을 체크하고, 또 다시 순회해 빙산을 녹이는 로직이 생각하기 제일 쉬우나, 사실 1번의 순회로 모두 체크할 수 있다.
이럼에도 계속 시간초과가 나서 고생했었는데, 문제 조건 중 "전부 다 녹을 때까지 두덩어리 이상 분리되지 않으면" 이라는 조건이 있다. 이 조건을 bfs() 마지막에서 체크해줬는데 이 부분이 빠지게 될 경우 main에서 bfs 반복을 탈출하지 못해 무한루프가 돌고 시간초과가 발생한다.
import java.io.*;
import java.util.*;
public class Main {
static int N, M, iceCount = 0;
static int[][] map, seaCount;
// 상 하 좌 우
static final int[] mx = {0, 0, -1, 1};
static final int[] my = {-1, 1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] != 0) iceCount++;
}
}
int year = 0;
while(bfs()) year++;
if(iceCount == 0) bw.write("0\n");
else bw.write(year + "\n");
bw.flush();
bw.close();
}
static boolean bfs() {
Queue<int[]> q = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
seaCount = new int[N][M];
int chunkCount = 0, steps = 0;
boolean flag = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(map[i][j] != 0 && !visited[i][j]) {
chunkCount++;
if(chunkCount >= 2) return false;
q.add(new int[]{i, j});
visited[i][j] = true;
while(!q.isEmpty()) {
int[] cur = q.remove();
int count = 0;
for (int k = 0; k < 4; k++) {
int ty = cur[0] + my[k];
int tx = cur[1] + mx[k];
if (ty >= 0 && ty < N && tx >= 0 && tx < M) {
if(!visited[ty][tx]) {
if(map[ty][tx] == 0) count++;
else {
visited[ty][tx] = true;
q.add(new int[]{ty, tx});
steps++;
}
}
}
}
seaCount[cur[0]][cur[1]] = count;
}
}
if(steps == iceCount) {
flag = true;
break;
}
}
if(flag) break;
}
iceCount = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(map[i][j] != 0) {
map[i][j] = Math.max(0, map[i][j] - seaCount[i][j]);
if(map[i][j] != 0) iceCount++;
}
}
}
return iceCount != 0;
}
}