[Java] 백준 BOJ / 2573번: 빙산

빙산

문제

---

문제 설명

N x M 크기의 격자에 물의 위치 0 과 한 덩어리로 이루어진 빙산들의 높이가 주어진다.

각각의 빙산들은 1년마다 물이 맞닿은 수 만큼 녹는다고 할 때 이 하나의 빙산 덩어리가 두개로 나눠지는 최초의 시간을 출력하고 다 녹을 때까지 분리되지 않는다면 0을 출력하는 문제이다.

---

구현

보자마자 지난번에 푼 치즈 문제와 비슷하다고 느꼈다.

코드를 짜기 전에 한 풀이 생각은 무한루프 내에서 빙산의 개수를 세고, 빙산을 물이 닿은 수만큼 감소시키는 거였는데 이렇게 한다면 바로바로 반영이 되기 때문에 만약에 빙산이였어도 다 녹아버린다면 다른 빙산에 영향을 주기 때문에 나중에 반영을 해야할 것 같아서 얼마나 감소할지는 따로 배열에 저장해두고 나중에 계산해주도록 했다.

일단 arr 라는 배열에 격자 정보를 입력받고나서 각 칸 마다 물이라면 그 주변 4칸을 확인해주며 만약에 빙산이라면 decrease 라는 배열에 얼마나 감소하는지를 저장한다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (arr[i][j] == 0) {
            for (int dir = 0; dir < 4; dir++) {
            	int nx = i + dx[dir];
                int ny = j + dy[dir];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                	continue;
				}
                if (arr[nx][ny] > 0) {
                	decrease[nx][ny]++;
                }
			}
		}
	}
}

이렇게 저장된 decrease 배열은 다시 한번 arr 배열을 돌면서 감소시켜주고 0 보다 작다면 0으로 바꿔준다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		arr[i][j] -= decrease[i][j];
		if (arr[i][j] < 0) {
			arr[i][j] = 0;
		}
	}
}

그리고 빙산의 개수를 세주는 함수에서는 visited 배열을 초기화 한후, arr 배열의 각 위치에서 bfs 함수를 실행한다.

public static int countIce() {
	visited = new boolean[n][m];
    int count = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
        	if (arr[i][j] > 0 && !visited[i][j]) {
          		bfs(i, j, visited);
                count++;
        	}
      	}
    }
    return count;
}

public static void bfs(int x, int y, boolean[][] visited) {
    queue = new LinkedList<>();
    queue.add(new int[]{x, y});
    visited[x][y] = true;

    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
  	    int curX = cur[0], curY = cur[1];
    	for (int dir = 0; dir < 4; dir++) {
			int nx = curX + dx[dir];
	        int ny = curY + dy[dir];
        	if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		    if (arr[nx][ny] > 0 && !visited[nx][ny]) {
        		visited[nx][ny] = true;
	            queue.add(new int[]{nx, ny});
			}
		}
	}
}

---

코드

import java.util.*;
import java.io.*;

public class Main_2573 {

  static int n, m;
  static int[][] arr;
  static int[][] decrease;
  static boolean[][] visited;
  static int[] dx = {-1, 0, 1, 0};
  static int[] dy = {0, -1, 0, 1};
  static int result = 0;
  static Queue<int[]> queue;

  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];

    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());
      }
    }

    while (true) {
      int count = countIce();
      if (count == 0) {
        System.out.println(0);
        return;
      }
      if (count >= 2) {
        System.out.println(result);
        return;
      }
      decrease = new int[n][m];
      // 물(0)인 곳들에서 주변을 확인
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          if (arr[i][j] == 0) {
            for (int dir = 0; dir < 4; dir++) {
              int nx = i + dx[dir];
              int ny = j + dy[dir];
              if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
              }
              if (arr[nx][ny] > 0) {
                decrease[nx][ny]++;
              }
            }
          }
        }
      }

      // 한 번에 빙산 줄이기
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          arr[i][j] -= decrease[i][j];
          if (arr[i][j] < 0) {
            arr[i][j] = 0;
          }
        }
      }
      result++;
    }
  }

  // ---------- 함수
  public static int countIce() {
    visited = new boolean[n][m];
    int count = 0;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (arr[i][j] > 0 && !visited[i][j]) {
          bfs(i, j, visited);
          count++;
        }
      }
    }
    return count;
  }

  public static void bfs(int x, int y, boolean[][] visited) {
    queue = new LinkedList<>();
    queue.add(new int[]{x, y});
    visited[x][y] = true;

    while (!queue.isEmpty()) {
      int[] cur = queue.poll();
      int curX = cur[0], curY = cur[1];
      for (int dir = 0; dir < 4; dir++) {
        int nx = curX + dx[dir];
        int ny = curY + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (arr[nx][ny] > 0 && !visited[nx][ny]) {
          visited[nx][ny] = true;
          queue.add(new int[]{nx, ny});
        }
      }
    }
  }
}