[ 백준/Java ] 2573. 빙산

백준 링크 : https://www.acmicpc.net/problem/2573

 

🌱 [ 문제 요약 ]

 

위와 같은 빙산이 있다. 숫자는 빙산의 높이 이며 숫자가 없는 칸은 바다이다.

1년마다 빙산이 높이가 줄어 든다. 빙산이 줄어드는 크기는 빙산의 상하좌우를 보았을 때 바다의 개수 이다.

빙산이 두개 이상의 묶음으로 나누어 지는 것은 몇년 후인가?

( 단. 빙산이 두개 이상으로 나누어 지지 않는다면 0을 출력 해야 한다. )

 

🔥  [ 주의 : 빙산이 녹을때 다른 빙산이 녹는 크기에 영향을 주지 않는다. ]

 

1년이 지날갈 때, 그림의 높이가 2인 빙산이 녹는다. 주위 바다가 2개 있으므로 이 빙산의 높이는 0이 된다.

 

같은 1년 이므로, 높이가 3인 빙산이 녹을때는 높이가 2인 빙산이 녹아서 바다가 된것을 포함 하지 않는다.

 

🌱 [ 문제 풀이 ]

[ 빙산 찾는법 ]

• 빙산 지도(map)을 돌며 빙산을 찾습니다. ( 크기가 1 이상이라면 빙산 )
• 빙산 묶음을 분리 하기 위해 boolean[ ][ ] visited를 사용 했습니다.
• 빙산을 찾은 경우 빙산 묶음을 찾기 위해 BFS를 수행 합니다.
• 빙산 묶음의 수를 올리고, 빙산을 녹이는 작업을 합니다.
• 빙산 묶음의 수를 반환 합니다.

static int findBingsan(){
        int bingsanCount = 0;
        for(int i = 0; i < map.length; i++){
            for(int j = 0; j < map[0].length; j++){
                if(!visited[i][j] && map[i][j] != 0){
                    bfs(i,j);
                    bingsanCount++;
                    melt();
                }
            }
        }
        return bingsanCount;
}

 

[ 빙산 묶음 찾는법 ]

• 빙산 묶음을 BFS를 통해 찾습니다.
• BFS 과정중 빙산이 녹을 크기도 같이 구합니다.
• 빙산의 좌표와 빙산이 녹을 크기를 meltList에 저장 합니다.

 static void bfs(int startRow, int startCol){
        Queue<Bingsan> queue = new LinkedList<>();
        Bingsan firstBingsan = new Bingsan(startRow, startCol);
        queue.add(firstBingsan);
        visited[startRow][startCol] = true;

        meltList = new ArrayList<>();
        while(!queue.isEmpty()) {
            Bingsan bingsan = queue.poll();

            int melt = 0;
            for (int i = 0; i < 4; i++) {
                int nextRow = bingsan.row + dx[i];
                int nextCol = bingsan.col + dy[i];

                if(isMapIn(nextRow, nextCol)){
                    if(!visited[nextRow][nextCol] && map[nextRow][nextCol] != 0) {
                        Bingsan nextBingsan = new Bingsan(nextRow, nextCol);
                        queue.add(nextBingsan);
                        visited[nextRow][nextCol] = true;
                    }

                    if(map[nextRow][nextCol] == 0){
                        melt++;
                    }
                }
            }

            if(melt > 0){
                meltList.add(new int[] {bingsan.row, bingsan.col, melt});
            }
        }
    }

 

[ 빙산 녹이는 법 ]

• meltList를 통해 빙산을 녹입니다.
• 녹인 빙산이 0보다 작을경우 0으로 바꾸어 줍니다.

private static void melt() {
        for(int i = 0; i < meltList.size(); i++){
            int[] melt = meltList.get(i);
            int row = melt[0];
            int col = melt[1];
            int meltCount = melt[2];

            map[row][col] -= meltCount;

            if(map[row][col] < 0){
                map[row][col] = 0;
            }
        }
}

 

[ 결과 출력 방법 ]

• 방문 배열은 매년마다 초기화 합니다.
• 빙산 묶음의 수를 반환 받고, 빙산 묶음이 없다면 년도를 0으로 바꿉니다.
• 이유는 빙산 묶음은 두개 이상일 경우 종료되므로 항상 한개 입니다.
• 만약 빙산 묶음이 없다면 한번에 녹은 것 입니다.

while(true){
	visited = new boolean[row][col];

	int bingsanCount = findBingsan();
	if(isZeroBingsanCount(bingsanCount)){
   		year = 0;
   		reak;
	}
	if(isTwoBingsanCount(bingsanCount)){
   		break;
	}
	year++;
}
System.out.println(year);

 

[ 전체 코드 ]

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class Bingsan2573 {
    static int[][] map;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][] visited;
    static List<int[]> meltList;
    static int row, col;
    static int year = 0;

    public static void main(String[] args) throws IOException {
        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][];

        // 맵 입력 받기
        for(int i = 0; i < row; i++){
            map[i] = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        while(true){
            visited = new boolean[row][col];

            int bingsanCount = findBingsan();
            if(isZeroBingsanCount(bingsanCount)){
                year = 0;
                break;
            }
            if(isTwoBingsanCount(bingsanCount)){
                break;
            }
            year++;
        }
        System.out.println(year);
    }

    static int findBingsan(){
        int bingsanCount = 0;
        for(int i = 0; i < map.length; i++){
            for(int j = 0; j < map[0].length; j++){
                if(!visited[i][j] && map[i][j] != 0){
                    bfs(i,j);
                    bingsanCount++;
                    melt();
                }
            }
        }
        return bingsanCount;
    }

    static void bfs(int startRow, int startCol){
        Queue<Bingsan> queue = new LinkedList<>();
        Bingsan firstBingsan = new Bingsan(startRow, startCol);
        queue.add(firstBingsan);
        visited[startRow][startCol] = true;

        meltList = new ArrayList<>();
        while(!queue.isEmpty()) {
            Bingsan bingsan = queue.poll();

            int melt = 0;
            for (int i = 0; i < 4; i++) {
                int nextRow = bingsan.row + dx[i];
                int nextCol = bingsan.col + dy[i];

                if(isMapIn(nextRow, nextCol)){
                    if(!visited[nextRow][nextCol] && map[nextRow][nextCol] != 0) {
                        Bingsan nextBingsan = new Bingsan(nextRow, nextCol);
                        queue.add(nextBingsan);
                        visited[nextRow][nextCol] = true;
                    }

                    if(map[nextRow][nextCol] == 0){
                        melt++;
                    }
                }
            }

            if(melt > 0){
                meltList.add(new int[] {bingsan.row, bingsan.col, melt});
            }
        }
    }

    private static void melt() {
        for(int i = 0; i < meltList.size(); i++){
            int[] melt = meltList.get(i);
            int row = melt[0];
            int col = melt[1];
            int meltCount = melt[2];

            map[row][col] -= meltCount;

            if(map[row][col] < 0){
                map[row][col] = 0;
            }
        }
    }

    static boolean isMapIn(int nextRow, int nextCol){
        return 0 <= nextRow && nextRow <= row -1 && 0 <= nextCol && nextCol <= col -1;
    }

    private static boolean isTwoBingsanCount(int bingsanCount) {
        return bingsanCount >= 2;
    }

    private static boolean isZeroBingsanCount(int bingsanCount) {
        return bingsanCount == 0;
    }

    static class Bingsan{
        private int row;
        private int col;

        public Bingsan(int row, int col){
            this.row = row;
            this.col = col;
        }
    }
}