Coding/알고리즘
[알고리즘 TIL] 2573. 빙산
kangplay
2025. 2. 24. 16:58
문제
https://www.acmicpc.net/problem/2573
설명
빙산이 두 개 이상의 덩어리로 분리되는 데 걸리는 년 수를 구하는 문제이다. 빙산이 그래프 형식으로 주어지므로, 그래프 탐색 알고리즘인 dfs를 이용했다.
dfs를 통해 0이 아닌 모든 노드를 방문하므로 같이 1년 후 빙산 배열에 대한 정보도 확인했다.
첫 번째 시도에서 오류가 발생했는데, 이유는 다음과 같았다.
import java.io.*;
import java.util.LinkedList;
public class Main {
static boolean[][] visited;
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
static int[][] icebergsNow;
static int[][] icebergsOneYearLater;
static LinkedList<int[]> stack;
static int N;
static int M;
static BufferedWriter bw;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] inputStr = br.readLine().split(" ");
N = Integer.parseInt(inputStr[0]);
M = Integer.parseInt(inputStr[1]);
icebergsNow = new int[N][M];
icebergsOneYearLater = new int[N][M];
for (int i = 0; i < N; i++) {
inputStr = br.readLine().split(" ");
for (int j = 0; j < M; j++) {
icebergsNow[i][j] = Integer.parseInt(inputStr[j]);
}
}
visited = new boolean[N][M];
int bundleCnt = 1;
int yearCnt = -1;
while (bundleCnt == 1) {
//덩어리 수가 0이거나 2 이상이면 종료
bundleCnt = 0;
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
if (icebergsNow[i][j] == 0) continue;
if (!visited[i][j]) {
dfs(i, j);
bundleCnt++;
}
}
}
yearCnt++;
//1년 후 데이터들로 초기화
icebergsNow = icebergsOneYearLater;
icebergsOneYearLater = new int[N][M];
visited = new boolean[N][M];
}
if (bundleCnt == 0) {
bw.write("0\n");
return;
} else {
bw.write(yearCnt + "\n");
}
bw.flush();
bw.close();
br.close();
}
private static void dfs(int n, int m) {
stack = new LinkedList<>();
stack.addLast(new int[]{n, m});
while (!stack.isEmpty()) {
int[] pos = stack.getLast();
stack.removeLast();
int y = pos[0];
int x = pos[1];
if (visited[y][x]) continue;
visited[y][x] = true;
checkNextHeight(y, x);
}
}
private static void checkNextHeight(int y, int x) {
int height = icebergsNow[y][x];
//높이가 0이면 스택에 더하지 않고 종료
if (height == 0) {
icebergsOneYearLater[y][x] = 0;
return;
}
//네 방향을 확인하여 1년 후 높이 계산
for (int i = 0; i < 4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
//유효한 좌표인지 확인
if (nextX < 0 || nextY < 0) continue;
//닿아있는 면이 바다(0)면 1년 후 높이를 1 줄임
if (icebergsNow[nextY][nextX] == 0) {
if (height > 0) height--;
} else {
//닿아있는 면이 빙산(1)이면 스택에 방문해야함을 저장
stack.addLast(new int[]{nextY, nextX});
}
}
//최종 높이를 1년 후 빙산 배열에 저장
icebergsOneYearLater[y][x] = height;
}
}- 범위 체크 오류
- nextX와 nextY의 0과 N,M에 대한 범위체크를 놓쳤다.
- 참조 값 복사
- iceburgs = iceburgsOneYearLater은 참조값 복사이므로 오류가 난다.
- 다음과 같이 값을 복사해주어야한다.
//1년 후 데이터들로 초기화
for (int i = 0; i < N; i++) {
System.arraycopy(icebergsOneYearLater[i], 0, icebergsNow[i], 0, M);
}- bw.write 후 바로 return
- bundleCnt가 0인 경우 예외 처리를 하였는데, 바로 return을 해서 출력이 없었다.
구현
최종적으로 성공한 코드는 다음과 같다.
import java.io.*;
import java.util.LinkedList;
public class Q2573_빙산_DFS {
static boolean[][] visited;
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
static int[][] icebergsNow;
static int[][] icebergsOneYearLater;
static LinkedList<int[]> stack;
static int N;
static int M;
static BufferedWriter bw;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] inputStr = br.readLine().split(" ");
N = Integer.parseInt(inputStr[0]);
M = Integer.parseInt(inputStr[1]);
icebergsNow = new int[N][M];
icebergsOneYearLater = new int[N][M];
for (int i = 0; i < N; i++) {
inputStr = br.readLine().split(" ");
for (int j = 0; j < M; j++) {
icebergsNow[i][j] = Integer.parseInt(inputStr[j]);
}
}
visited = new boolean[N][M];
int bundleCnt = 1;
int yearCnt = -1;
while (bundleCnt == 1) {
//덩어리 수가 0이거나 2 이상이면 종료
bundleCnt = 0;
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
if (icebergsNow[i][j] == 0) continue;
if (!visited[i][j]) {
dfs(i, j);
bundleCnt++;
}
}
}
yearCnt++;
//1년 후 데이터들로 초기화
for (int i = 0; i < N; i++) {
System.arraycopy(icebergsOneYearLater[i], 0, icebergsNow[i], 0, M);
}
icebergsOneYearLater = new int[N][M];
visited = new boolean[N][M];
}
if (bundleCnt == 0) {
bw.write("0\n");
} else {
bw.write(yearCnt + "\n");
}
bw.flush();
bw.close();
br.close();
}
private static void dfs(int n, int m) {
stack = new LinkedList<>();
stack.addLast(new int[]{n, m});
while (!stack.isEmpty()) {
int[] pos = stack.getLast();
stack.removeLast();
int y = pos[0];
int x = pos[1];
if (visited[y][x]) continue;
visited[y][x] = true;
checkNextHeight(y, x);
}
}
private static void checkNextHeight(int y, int x) {
int height = icebergsNow[y][x];
//높이가 0이면 스택에 더하지 않고 종료
if (height == 0) {
icebergsOneYearLater[y][x] = 0;
return;
}
//네 방향을 확인하여 1년 후 높이 계산
for (int i = 0; i < 4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
//유효한 좌표인지 확인
if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) continue;
//닿아있는 면이 바다(0)면 1년 후 높이를 1 줄임
if (icebergsNow[nextY][nextX] == 0) {
if (height > 0) height--;
} else {
//닿아있는 면이 빙산(1)이면 스택에 다음 좌표 저장
stack.addLast(new int[]{nextY, nextX});
}
}
//최종 높이를 1년 후 빙산 배열에 저장
icebergsOneYearLater[y][x] = height;
}
}