[BOJ] 백준 [2573] 빙산 JAVA

https://www.acmicpc.net/problem/2573

2573번: 빙산

📝문제

📝풀이

탐색문제인데 , 탐색할 때 마다 다른 노드에 영향을 끼치는 유형이며 큐를 이용해야 하는 문제이다.

isSeprated() 함수로 분리가 되었는지에 대한 검사를 계속 시행하면서
만약 분리가 되지 않은 경우 전 좌표를 살피면서 동서남북으로 바다가 있는지 검사한다.
검사한 결과가 0보다 클 경우 큐에 삽입.

if 큐가 비어있을 경우 => 분리 불가능. break

 

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

import static java.util.Arrays.stream;


public class Main {

    static int[] dx={0,0,1,-1},dy={1,-1,0,0};
    static int w,h;
    static int[][] map;
    static boolean[][] visit;

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

        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        map = new int[h][w];
        for(int i=0;i<h;i++){
            map[i] = stream(br.readLine().split(" "))
                                .mapToInt(Integer::parseInt)
                                .toArray();

        } // end input

        int answer=0;

        while (!isSeparate()){

            LinkedList<int[]> q = new LinkedList<>();

            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(map[i][j]>0){
                        q.add(new int[]{j,i, countNearBy(j, i)}); // x,y,count
                    }
                }
            }

            if (q.isEmpty()) {
                answer = 0;
                break;
            }

            while (!q.isEmpty()){
                int[] cur = q.poll();
                int x = cur[0];
                int y = cur[1];
                int cnt = cur[2];
                map[y][x] = map[y][x] > cnt? map[y][x]-cnt : 0;
            }
            answer++;
        }

        System.out.println(answer);

    }

    static boolean isRange(int x,int y){

        return x>=0&&y>=0&&x<w&&y<h;
    }
    static int countNearBy(int x,int y){

        return (int) IntStream.range(0, 4)
                .filter(i -> isRange(x, y))
                .filter(i->map[y + dy[i]][x + dx[i]] == 0)
                .count();
    }
    static boolean isSeparate(){

        visit = new boolean[h][w];
        int cnt=0;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(!visit[i][j] && map[i][j]!=0) {
                    dfs(j, i, visit);
                    cnt++;
                }
            }
        }
        return cnt>1;
    }

    static void dfs(int x,int y,boolean[][] visit){

        visit[y][x]=true;

        for(int i=0;i<dx.length;i++){

            int nextX = x+dx[i];
            int nextY = y+dy[i];

            if(isRange(nextX,nextY) && map[nextY][nextX]!=0 && !visit[nextY][nextX])
                dfs(nextX,nextY,visit);
        }
    }
}