[백준] 2573번 : 빙산 - 자바(JAVA)

https://www.acmicpc.net/problem/2573

2573번: 빙산

 

문제 해석

각 빙산의 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장됩니다.

빙상 이외에 바다에 해당하는 칸에는 0이 저장됩니다.

빙산의 높이는 바닷물에 많이 접해져 있는 부분부터 빨리 줄어듭니다.

배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 각 칸에 동서남북 4 방향으로 붙어 있는 0이 저장된 캉의 개수만큼 줄어듭니다.

 

그림1의 빙산은 1년후에 그림 2와 같이 변형됩니다.

그림2의 빙산은 1년후에 다음과 같이 변합니다.

문제 풀이 전 설계

1. 모든칸을 DFS 돌면서 분리된 빙산이 존재하는것을 찾습니다. (만약 분리된 빙산이 존재한다면 끝냅니다.)

2. 모든 빙산의 상하좌우 인접한 바다의 개수를 확인하는 작업을 먼저 합니다. O(300*300 * 4)

3. 그 개수만큼 빙산의 크기를 줄여줍니다. O(300*300)

 

종료조건 : 빙산이 분리되는 시점 또는 모든 빙산이 다 녹을때까지

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2573_빙산 {

    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int height, width;
    static int[][] board,ocean;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        height = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());

        board = new int[height][width];

        for (int y = 0; y < height; y++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int x = 0; x < width; x++) {
                board[y][x] = Integer.parseInt(st.nextToken());
            }
        }
        //입력 끝
        int time = 0;

        while (!isAllMelt()) {

            if (!isUnion()) {
                System.out.println(time);
                return;
            }

            ocean = new int[height][width];
            checkOceanCount();
            downSizing();
            time++;
        }

        System.out.println(0);


    }

    private static boolean isAllMelt() {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (board[y][x] != 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean isUnion() {
        int count = 0;
        visited = new boolean[height][width];

        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (board[y][x] == 0 || visited[y][x]) {
                    continue;
                }
                if (count != 0) {
                    return false;
                }
                dfs(y, x);
                count++;
            }
        }
        return true;
    }

    private static void dfs(int y, int x) {
        visited[y][x] = true;

        for (int direction = 0; direction < 4; direction++) {
            int ny = y + dy[direction];
            int nx = x + dx[direction];
            if (!isNextValid(ny, nx)) {
                continue;
            }
            dfs(ny, nx);
        }

    }

    private static boolean isNextValid(int ny, int nx) {
        return ny >= 0 && nx >= 0 && ny < height && nx < width && board[ny][nx] != 0 && !visited[ny][nx];
    }

    private static void checkOceanCount() {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {

                if(board[y][x] == 0){
                    continue;
                }

                for (int direction = 0; direction < 4; direction++) {
                    int ny = y + dy[direction];
                    int nx = x + dx[direction];
                    if (!isOceanValid(ny, nx)) {
                        continue;
                    }
                    ocean[y][x]++;
                }
            }
        }
    }

    private static boolean isOceanValid(int ny, int nx){
        return ny >= 0 && nx >= 0 && ny < height && nx < width && board[ny][nx] == 0;
    }

    private static void downSizing() {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if(board[y][x] == 0){
                    continue;
                }

                //System.out.println(board[y][x] + " " + ocean[y][x]);
                board[y][x] = board[y][x] - ocean[y][x];

                //음수인경우에는 board[y][x] = 0
                board[y][x] = board[y][x] < 0 ? 0 : board[y][x];

            }

        }
    }

}