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

 

2573번: 빙산

 

 

👇 내가 제출한 코드

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

public class Main {
    static int N, M;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static int[][] ocean;
    static boolean[][] visited;
    static List<int[]> icebergs = new ArrayList<>();

    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());
        ocean = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                ocean[i][j] = Integer.parseInt(st.nextToken());
                if(ocean[i][j] > 0) {
                    icebergs.add(new int[] {i, j}); // 빙산 좌표 저장
                }
            }
        }

        int time = 0;
        while(!icebergs.isEmpty()){
            time++; // 빙산 분리되는 시간
            melting(); // 빙산 녹이기

            if(searchSplit()) {
                System.out.println(time);
                return;
            }
        }
        System.out.println(0);
    }
    public static void melting() {
        int[][] tempMap = new int[N][M];
        List<int[]> nextIcebergs = new ArrayList<>();

        // 빙산 좌표 돌면서 얼마나 녹일지 확인하기
        for(int[] iceberg : icebergs) {
            int x = iceberg[0];
            int y = iceberg[1];

            int melt = 0;
            for(int d = 0; d < 4; d++) {
                int nx = dr[d] + x;
                int ny = dc[d] + y;

                if(nx >= 0 && ny >= 0 && nx < N && ny < M && ocean[nx][ny] == 0) melt++;
            }
            // 녹인 후 빙산의 높이 임시배열에 저장해두기
            tempMap[x][y] = Math.max(0, ocean[x][y] - melt);
            // 다 녹지 않았다면 좌표 저장
            if(tempMap[x][y] > 0) nextIcebergs.add(new int[] {x, y});
        }

        icebergs = nextIcebergs; // 빙산 좌표 갱신
        // 임시배열 반영하기
        for(int i = 0; i < N; i++) {
            System.arraycopy(tempMap[i], 0, ocean[i], 0, M);
        }
    }

    public static boolean searchSplit() {
        int count = 0;
        for(boolean[] row : visited) Arrays.fill(row, false); // 방문 판별 배열 초기화

        // 빙산 좌표만 dfs 돌면서 분리된 덩어리 개수 확인하기
        for(int[] iceberg : icebergs) {
            int x = iceberg[0];
            int y = iceberg[1];

            if(!visited[x][y]) {
                dfs(x, y);
                count++; // 분리된 덩어리 개수
                if(count > 1) return true;
            }
        }
        return false;
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;
        for(int d = 0; d < 4; d++) {
            int nx = dr[d] + x;
            int ny = dc[d] + y;

            if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && ocean[nx][ny] > 0) {
                dfs(nx, ny);
            }
        }
    }
}

 

 

느낀 점 및 정리 ✍️

1. 처음에 작성했던 코드는 분리된 빙산의 개수를 찾을 때 배열의 처음부터 끝까지 돌면서 dfs로 확인했었다. 그래서인지 59%에서 자꾸 시간초과가 떴었던 것 같기도.... ㅠㅠ

2. System.arrayscopy 메소드 아직 익숙하지 않아서 찾아봐야겠다. 원래 clone()만 썼었는데 무슨 차이가 있는지도 확인해봐야겠다.