[Gold IV] 빙산 - 2573

성능 요약

메모리: 25000 KB, 시간: 404 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현

제출 일자

2024년 8월 24일 20:36:46

문제 설명

<p>지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.</p>

<p>그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.</p>

<p>한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.</p>

입력

출력

풀이

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

class Main {
    static int row;
    static int col;
    static int[][] map;
    static int[][] visited;
    static int[][] melt;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        
        map = new int[row][col];
        visited = new int[row][col];
        melt = new int[row][col];

        for (int i=0; i<row; i++) { // 빙산 배열
            st= new StringTokenizer(br.readLine());
            for(int j=0; j<col; j++) {
                map[i][j]= Integer.parseInt(st.nextToken());
            }
        }

        answer();
    }
 
    static void answer() {
        int year= 0;
        while (true) {
            int count= 0;
            for (int i=0; i<row; i++) {
                for (int j=0; j<col; j++) {
                    if(visited[i][j]= 0 && map[i][j] = 0) { // 방문하지 않았고 빙산이 있는 경우
                        dfs(i, j);
                        count++;
                    }
                }
            }

            // 빙산이 모두 녹은 경우
            if (count= 0) {
                System.out.println(0);
                break;
            } else if (count >= 2) { // 빙산 덩어리가 2개 이상인 경우
                System.out.println(year);
                break;
            }

            melting();
            year++;
        }
    }

    // dfs
    static void dfs(int x, int y) {
        visited[x][y] = 1;
        for(int i=0; i<4; i++) {
            int nx= x + dx[i];
            int ny= y + dy[i];
            if (0<=nx && nx<row && 0<=ny && ny<col) { // 1년 후에 녹는 빙산의 양
                if(map[nx][ny]= 0)
                    melt[x][y]++;
                if (visited[nx][ny=0 && map[nx][ny]=0) // 방문하지 않았고 빙산이 있는 경우
                    dfs(nx, ny);                    
            }
        }
    }

    // 빙산 녹임
    static void melting() {
        for(int i=0; i<row; i++) {
            for(int j=0; j<col; j++) {
                map[i][j] = melt[i][j]; // 빙산 높이에서 녹은 양 뺌
                if(map[i][j] < 0)
                    map[i][j]= 0; // 높이가 음수가 되면 0으로 설정
                visited[i][j]= 0;
                melt[i][j]= 0;
            }
        }
    }
}

[Gold IV] 빙산 - 2573

성능 요약

분류

제출 일자

문제 설명

입력

출력

풀이

댓글