링크

2573 빙산

문제

풀이

빡구현 같은 느낌이다. 어렵진 않았지만 시간이 오래 걸렸다.
1. map배열을 복사해놓고 주위에 빙하가 있는지 없는지 판단한다.
2. 녹은 값을 새로운 2차 배열에 저장해둔다.
3. 새로운 2차배열을 map에다가 뒤집어씌운다.
4. bfs를 통해 빙하가 몇덩어리인지 체크한다.

이렇게 풀어나갔다

코드

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

public class Main{
    public static int[] dx = {1, 0, -1, 0};
    public static int[] dy = {0, 1, 0, -1};

    public static int[][] map;

    public static int year = 0;

    public static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int N = Integer.parseInt(arr[0]);
        int M = Integer.parseInt(arr[1]);

        map = new int[N][M];
        for(int i=0;i<map.length;i++){
            arr = br.readLine().split(" ");

            for(int j=0;j<arr.length;j++){
                map[i][j] = Integer.parseInt(arr[j]);
            }
        }

        while(true){
            changeYear();
            if(iceGroup()){
               if(allZeroCheck()){
                   System.out.println(0);
               } else{
                   System.out.println(year);
               }

                break;
            }
        }

    }

    public static void changeYear(){
        int[][] newMap = new int[map.length][map[0].length];

        //맵 복사
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                newMap[i][j] = map[i][j];
            }
        }

        //0이 아니면 사방에 0이 있는지 체크해서 빼주기
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                if(map[i][j] != 0){
                    int iceMelt = 0;

                    for(int k=0;k<4;k++){
                        int newX = i + dx[k];
                        int newY = j + dy[k];

                        if(newX < 0 || newY < 0 || newX >= map.length || newY >= map[0].length) continue;

                        if(map[newX][newY] == 0){
                            iceMelt++;
                        }

                    }

                    if(newMap[i][j] - iceMelt <= 0){
                        newMap[i][j] = 0;
                    } else{
                        newMap[i][j] -= iceMelt;
                    }

                }
            }
        }

        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                map[i][j] = newMap[i][j];
            }
        }


    }

    //몇덩어리?
    //분리안되고 다 녹으면 0을 리턴해야됨
    public static boolean iceGroup(){
        year++;

        int iceCount = 0;
        boolean[][] visited = new boolean[map.length][map[0].length];


        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                if(map[i][j] != 0 && !visited[i][j]){
                    Queue<Integer> queue = new LinkedList<>();
                    queue.add(i);
                    queue.add(j);
                    visited[i][j] = true;

                    while(!queue.isEmpty()){
                        int x = queue.poll();
                        int y = queue.poll();

                        for(int k=0;k<4;k++){
                            int newX = x + dx[k];
                            int newY = y + dy[k];

                            if(newX < 0 || newY < 0 || newX >= map.length || newY >= map[0].length) continue;

                            if(!visited[newX][newY] && map[newX][newY] != 0){
                                visited[newX][newY] = true;
                                queue.add(newX);
                                queue.add(newY);
                            }

                        }
                    }

                    iceCount++;
                }
            }
        }

        if(allZeroCheck()){
            return true;
        }

        if(iceCount >= 2){
            return true;
        }

        return false;

    }


    public static boolean allZeroCheck(){
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                if(map[i][j] != 0) return false;
            }
        }

        return true;
    }



}