빙산

📍 문제 설명

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

2573번: 빙산

 

💡 접근

bfs 문제였는데 큐가 2가지 필요했다.

1. 빙산을 한번에 녹이기 위한 큐

2. 두 덩어리 이상으로 분리되어있는지 확인하기 위한 큐

 

👩‍💻 코드

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

public class Main {
    static int[] arr, dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static int[][] board;
    static boolean[][] visited;
    static int n, m, k, t, num, cnt, second;
    static ArrayList<Integer> list = new ArrayList<>();
    static Queue<Point> q = new LinkedList<>();

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j] != 0) q.add(new Point(i, j, board[i][j]));
            }
        }

        System.out.println(bfs());
    }

    private static int bfs() {
        while (!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                Point cp = q.poll();

                int cnt = 0;
                //상하좌우 확인해서 바닷물 몇 개인지 확인
                for(int j = 0; j < 4; j++) {
                    int nx = cp.x + dx[j];
                    int ny = cp.y + dy[j];
                    if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
                    if(board[nx][ny] == 0) cnt++;
                }
                //일단 바닷물 갯수만큼 빼서 큐에 다시 넣어놓기
                q.offer(new Point(cp.x, cp.y, board[cp.x][cp.y]-cnt));
            }

            //모든 좌표 다 확인했으면 원배열을 갱신시켜주기
            for(int i = 0; i < len; i++) {
                Point cp = q.poll();
                board[cp.x][cp.y] = cp.cnt < 0 ? 0 : cp.cnt;
                //빙산이 남아있을 때만 큐에 다시 넣어주기
                if(cp.cnt > 0) q.offer(new Point(cp.x, cp.y, board[cp.x][cp.y]));
            }
            second++;
            //두 덩어리 이상으로 분리되는지 확인
            if(isMany()) return second;
        }
        return 0;
    }

    private static boolean isMany() {
        visited = new boolean[n][m];
        cnt = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                //인접한 빙산 모두 방문처리
                if(board[i][j] > 0 && !visited[i][j]) {
                    bfs2(i, j);
                    cnt++;
                }
            }
            if(cnt >= 2) return true;
        }
        return false;
    }

    private static void bfs2(int x, int y) {
        Queue<Point> mq = new LinkedList<>();
        mq.offer(new Point(x, y));
        while(!mq.isEmpty()) {
            Point cp = mq.poll();
            for(int i = 0; i < 4; i++) {
                int nx = cp.x + dx[i];
                int ny = cp.y + dy[i];

                if(nx<0 || ny<0 || nx>=n || ny>=m || visited[nx][ny] || board[nx][ny] == 0) continue;
                visited[nx][ny] = true;
                mq.offer(new Point(nx, ny));
            }
        }
    }

    private static class Point {
        private int x;
        private int y;
        private int cnt;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Point(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    ", cnt=" + cnt +
                    '}';
        }
    }
}