[백준] 2573번: 빙산 - JAVA

 

 

문제

 

 

 

풀이

 

한 개의 빙산이 두 개 이상의 빙산으로 쪼개지는 데 걸리는 시간을 구하는 문제이다.

빙산의 개수를 구하는 Method, 빙산을 녹이는 Method로 나누어서 풀이했다.

 

행의 개수 N, 열의 개수 M을 입력받는다. 

N x M의 크기를 가지는 2차원 Integer 배열을 선언하고 입력값을 저장한다.

 

얼음이 다 녹을 때까지 반복하며 빙산 덩어리의 수를 확인한다. 빙산 덩어리가 1개 초과라면 반복된 날짜를 출력한다.

빙산 덩어리가 1개라면 얼음을 녹인다.

영역을 순회하며 얼음을 찾는다.

인접된 영역이 물인 수만큼 얼음을 녹인다. 이 때, 먼저 확인한 얼음이 녹아 물이 된 경우에는 녹이지 않는다.

 

아래 그림에서 3인 얼음의 인접인 물이 3이기 때문에 물이되지만 4인 얼음은 인접 물 3개의 영향만 받는다.

 

얼음이 다 녹았는데 빙산 덩어리가 1개를 초과하지 않으면 0을 출력한다.

 

 

정답 코드

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

public class Main {
	static int N;
    static int M;
    static int[][] map;
    static boolean[][] visited;
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};

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

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int day = 0;
        while(true) {
            visited = new boolean[N][M];
            int count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > 0 && !visited[i][j]) {
                        count++;
                        visited[i][j] = true;
                        find(i, j);
                    }
                }
            }
            if(count > 1) {
                System.out.println(day);
                break;
            }
            day++;
            boolean isChange = false;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > 0) {
                        isChange = true;
                        melt(i, j);
                    }
                }
            }

            if(!isChange) {
                System.out.println(0);
                break;
            }
        }
    }

    // 이번 시퀀스에서 인접지역이 얼음이 아닌 영역만큼 얼음을 녹인다.
    static void melt(int i, int j) {
        for(int k = 0; k < 4; k++) {
            int newI = i + dx[k];
            int newJ = j + dy[k];

            if(newI >= 0 && newI < N && newJ >= 0 && newJ < M && map[newI][newJ] == 0 && map[i][j] > 0 && !visited[newI][newJ]) {
                map[i][j]--;
            }

        }
    }

    // 인접된 영역을 찾아 방문 영역으로 입력한다.
    static void find(int i, int j) {
        for(int k = 0; k < 4; k++) {
            int newI = i + dx[k];
            int newJ = j + dy[k];
            if (newI >= 0 && newI < N && newJ >= 0 && newJ < M && map[newI][newJ] > 0 && map[i][j]  > 0 && !visited[newI][newJ]) {
                visited[newI][newJ] = true;
                find(newI, newJ);
            }
        }
    }
}

 

 

문의사항이나 피드백은 댓글로 남겨주세요.