[백준 2573번][Java] 빙산 - 구현, 그래프

www.acmicpc.net/problem/2573

2573번: 빙산

 

쉬울 줄 알고 덤볐다가 꽤 시간을 잡아 먹은 문제입니다.

문제를 살펴보면 해야될 작업이 딱 두 가지가 떠오를 겁니다.

 

1. 쪼개지는 빙산의 개수 구하기

2. 배열을 순회하면서 얼음 녹이기

 

1번은 전형적인 그래프 컴포넌트 개수 구하기 문제입니다. 2번은 하나의 좌표가 주어질 때, 상하좌우에 0이 있는 개수만큼 값을 빼주면 되고요.

 

저는 1,2번 작업을 분리시켜서 구현했었는데, 시간 초과가 발생했습니다.

그래서 1번을 진행하는 중에 nextIceberg 라는 2차원 배열에 2번 계산값을 기록하도록 했습니다. 1번 과정을 끝내고 빙산이 쪼개지지 않았다면 nextIceberg를 다시 Iceberg에 기록하면 되겠지용.

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/*
빙산
https://www.acmicpc.net/problem/2573
 */
public class Main {
    static int N,M;
    public static void main(String[] args) throws IOException {
//        InputReader reader = new InputReader("testcase.txt");
        InputReader reader = new InputReader();
        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int[][] iceberg = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(reader.readLine());
            for (int j = 0; j < M; j++) {
                iceberg[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int passedYear = 0;

        while(true) {
            int componentCount = melt(iceberg);
            //빙산이 2개 이상으로 쪼개지는 경우
            if(componentCount >= 2) {
                System.out.println(passedYear);
                return;
            }
            //빙산이 2개 이상으로 쪼개지지 않은 상태에서 모두 녹은 경우
            if(componentCount == 0) {
                System.out.println(0);
                return;
            }
            passedYear++;
        }
    }


    private static int melt(int[][] iceberg) {
        int[][] nextIceberg = new int[N][M];
        boolean[][] visited = new boolean[N][M];
        
        //컴포넌트 개수 파악, 다음 빙산 배열 정보 기록을 동시에
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(iceberg[i][j] > 0 && !visited[i][j]) {
                    if(count > 1) return count; //컴포넌트가 2 이상이면 바로 종료
                    dfs(i,j,visited, iceberg, nextIceberg);
                    count++;
                }
            }
        }
        
        //여기까지 왔다면 컴포넌트가 하나인 상태, 기록했던 nextIceberg 값을 다시 iceberg 에 저장 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                iceberg[i][j] = nextIceberg[i][j];
            }
        }

        return count;
    }

    static int[] dr = {0,0,1,-1};
    static int[] dc = {1,-1,0,0};
    private static void dfs(int row, int col, boolean[][] visited, int[][] iceberg, int[][] nextIceberg) {
        visited[row][col] = true;
        
        //현재 빙산의 정보를 이용해 녹인후 다음 빙산 배열에 저장
        int meltSpeed = countMeltingWays(row, col, iceberg);
        int meltAmount = iceberg[row][col]-meltSpeed ;
        nextIceberg[row][col] = meltAmount < 0 ? 0 : meltAmount;

        for (int i = 0; i < 4; i++) {
            int nextRow = row+dr[i];
            int nextCol = col+dc[i];
            if(isRange(nextRow, nextCol) && !visited[nextRow][nextCol] && iceberg[nextRow][nextCol] > 0) {
                dfs(nextRow, nextCol, visited, iceberg, nextIceberg);
            }
        }
    }

    private static boolean isRange(int row, int col) {
        if(row < 0 || row >= N || col < 0 || col >= M) return false;
        return true;
    }

    private static int countMeltingWays(int row, int col, int[][] iceberg) {
        int meltSpeed = 0;
        for (int i = 0; i < 4; i++) {
            int nextRow = row+dr[i];
            int nextCol = col+dc[i];
            if(isRange(nextRow, nextCol) && iceberg[nextRow][nextCol] == 0) meltSpeed++;
        }
        return meltSpeed;
    }
}

class InputReader {
    private BufferedReader br;

    public InputReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public InputReader(String filepath) {
        try {
            br = new BufferedReader(new FileReader(filepath));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public List<Character> readLineIntoCharList() throws IOException {
        List<Character> l = new ArrayList<>();
        while(true) {
            int readVal = br.read();
            if(readVal == '\n' || readVal == -1) break;
            l.add((char)readVal);
        }
        return l;
    }

    public boolean ready() throws IOException {
        return br.ready();
    }

    public String readLine() throws IOException {
        return br.readLine();
    }
    public int readInt() throws IOException {
        return Integer.parseInt(readLine());
    }
    public Long readLong() throws IOException {
        return Long.parseLong(readLine());
    }
}