백준 2573번
https://www.acmicpc.net/problem/2573
private static boolean globalWarming() {
// 0밖에 없는지 체크
boolean zeroAnotherNumberCheck = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] > 0) {
int count = 0;
// 4가지 방향을 탐색해서 갈 수 바다와 접한 부분 하나씩 감소
for (int k = 0; k < 4; k++) {
int nowX = i + dirX[k];
int nowY = j + dirY[k];
if (rangeCheck(nowX, nowY) && arr[nowX][nowY] == 0) {
count++;
}
}
if(arr[i][j] - count <= 0) {
tempArr[i][j] = 0;
} else {
tempArr[i][j] = arr[i][j] - count;
zeroAnotherNumberCheck = true;
}
}
}
}
if(!zeroAnotherNumberCheck) {
return false;
}
copy(); // 계산 된 빙산을 다시 복사
return true;
} // End of globalWarming
이 문제의 핵심은 빙산이 1년 단위로 녹는 과정을 구현하는 것이다.
처음에 빙산을 1년이 증가할 때, 0을 초과하는 값을 찾고 0과 접하는 부분을 기준으로 - 1씩 하도록 해줬는데, 이렇게 할 경우 빙산이 녹아서 0이 될 경우, 다음 계산을 할 빙산이 이전의 0이 된 값의 영향을 받기 때문에, 녹는 빙산의 계산은 다른 2차원 배열에서 계산하여 복사는 방식으로 진행해줬다.
빙산이 2개 이상의 영역이 되면 곧바로 중지를 하면 되지만, 빙산이 모두 녹을 때 까지 2개 이상의 영역이 되지 못하면, 정답이 0이 되어야 하기 때문에 마지막 빙산의 녹는 과정이 끝나고 난 후 현재 배열이 0으로만 이뤄져 있는지도 파악해야 한다.
그래서 zeroAnotherNumberCheck
변수를 하나 만들어 두고 0이 아닌 값이 들어왔을 때, true로 변환해서 알 수 있도록 만들었다
import java.lang.reflect.Array;
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[][] arr;
static int[][] tempArr;
static boolean[][] isVisited;
static int[] dirX = {0, 0, -1, 1};
static int[] dirY = {-1, 1, 0, 0};
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());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
tempArr = new int[N][M];
int highestHeightIceberg = -1;
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());
highestHeightIceberg = Math.max(highestHeightIceberg, arr[i][j]);
}
}
int area = 0;
int year = 0;
for (;;) {
if (year > 0) {
if(!globalWarming()) {
System.out.println(0);
return;
}
area = 0;
}
isVisited = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] > 0 && !isVisited[i][j]) {
area++;
DFS(i, j);
}
if (area >= 2) {
System.out.println(year);
return;
}
}
}
year++;
}
} // End of main
private static void DFS(int x, int y) {
isVisited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nowX = x + dirX[i];
int nowY = y + dirY[i];
if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && arr[nowX][nowY] > 0) {
DFS(nowX, nowY);
}
}
} // End of DFS
private static boolean rangeCheck(int nowX, int nowY) {
return nowX >= 0 && nowX < N && nowY >= 0 && nowY < M;
} // End of rangeCheck
private static boolean globalWarming() {
// 0밖에 없는지 체크
boolean zeroAnotherNumberCheck = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] > 0) {
int count = 0;
// 4가지 방향을 탐색해서 갈 수 바다와 접한 부분 하나씩 감소
for (int k = 0; k < 4; k++) {
int nowX = i + dirX[k];
int nowY = j + dirY[k];
if (rangeCheck(nowX, nowY) && arr[nowX][nowY] == 0) {
count++;
}
}
if(arr[i][j] - count <= 0) {
tempArr[i][j] = 0;
} else {
tempArr[i][j] = arr[i][j] - count;
zeroAnotherNumberCheck = true;
}
}
}
}
if(!zeroAnotherNumberCheck) {
return false;
}
copy(); // 계산 된 빙산을 다시 복사
return true;
} // End of globalWarming
private static void copy() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
arr[i][j] = tempArr[i][j];
}
}
} // End of copy
} // End of Main class