[백준] 2573번 빙산 Java

dustle·2023년 3월 22일
1

빙산

빙산의 개수 판별과 빙산 녹이기를 해결해야 하는 문제입니다.
bfs를 사용하여 인접한 솟아있는 빙산을 판별하며 큐에 집어넣고 방문처리를 했으며
인접한 배열이 0일경우 하나씩 녹이기를 if문과 else if문으로 나눠서 처리했습니다.

그냥 녹여버리면 주변 빙하가 갑자기 0이 됐을 때 그것도 포함하여 녹아야할 숫자가 합산되어버리므로,복사본을 만들고 추후에 깊은 복사를 사용해 옮겨야합니다.

하나의 bfs를 한 후 이중 for문을 돌며 솟아있으며 방문처리가 안된 배열은 동떨어진 빙산이므로(아까 bfs로 처리가 안된 빙산)
bfs가 돌아간 개수를 세어 1개 초과일 때 while문을 탈출하게 만들고,
bfs가 돌아간 개수가 0일 경우 빙산이 모두 녹아있는 상태이므로 days에 0을 집어넣고 탈출하게 구현했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
    public static int N;
    public static int M;
    public static int[] X = {1, -1, 0, 0};//동서남북
    public static int[] Y = {0, 0, -1, 1};
    public static int[][] map;
    public static int[][] copy;
    public static boolean[][] visited;
    public static Queue<Xy> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        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];
        copy = 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++) {
                int tmp = Integer.parseInt(st.nextToken());
                map[i][j] = tmp;
                copy[i][j] = tmp;
                visited[i][j] = false;
            }
        }

        int num = 0;
        int days = 0;

        while (true){
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > 0 && !visited[i][j]) {
                        bfs(i, j);
                        num++;//bfs문 돌은 개수(빙산 개수) 체크
                        copyToMap();
                    }
                }
            }


            if(num > 1) break; //bfs문이 한개 초과 돌았으면 빙산이 여러 개이다
            else if(num == 0){//bfs문이 하나도 안돌았다는건 빙산 높이 있는 곳이 없다는 거니깐 0으로 내버리기
                days = 0;
                break;
            }
            makeFalse();
            num = 0;
            days++;
        }

        System.out.println(days);

    }

    private static void makeFalse() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = false;
            }
        }
    }

    private static void copyToMap() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = copy[i][j];
            }
        }
    }


    private static void bfs(int n, int m) {
        queue.offer(new Xy(n, m));
        visited[n][m] = true;

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

            for (int i = 0; i < 4; i++) {
                x = X[i];
                y = Y[i];

                if (map[(tmp.x + x)][(tmp.y + y)] > 0 && visited[(tmp.x + x)][(tmp.y + y)] == false) {
                    visited[(tmp.x + x)][(tmp.y + y)] = true;
                    queue.offer(new Xy((tmp.x + x), (tmp.y + y)));//빙하 한 덩어리 판별용
                } else if (map[(tmp.x + x)][(tmp.y + y)] == 0 && copy[tmp.x][tmp.y] > 0) {
                    copy[tmp.x][tmp.y]--;//얼음 녹이기
                }
            }
        }
    }

    private static class Xy {
        private int x;
        private int y;

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

0개의 댓글