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

문제

0에 상하좌우로 인접하면 인접한 면마다 -1처리
호수도 바다로 취급

풀이

두 함수로 나눠서 풀이한다

• melting
• check

melting()

• map에서 0을 찾고 인접한 빙산에 -1를 한다.
• 만약 1인 빙산을 0을 만들었을 때 0을 바다로 인식하지 않기위해 visit 배열을 사용하였다.

check()

• map에서 빙산을 찾고 BFS를 진행하고 또 다른 빙산을 찾으면 true를 return한다.

코드

 public static void pro() {
        ans = 0;
        for (int year = 0; year <= 1500; year++) {
            // 빙산 나눠졌는지 확인
            if (check()) {
                ans = year;
                break;
            }
            // 바다 인접부분 녹게하기
            melting();
        }
        System.out.println(ans);
    }

처음부터 빙산이 여러개일 수 있으니 check를 먼저 진행하고 melting진행
주어진 입력의 범위를 계산하여 반복횟수를 정한다.

전체코드

package baekjoon._2573;

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 void main(String[] args) {
        input();
        pro();
    }

    static int N, M, ans, max;
    static int[][] map;
    static boolean[][] visit;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static Queue<int[]> queue;

    public static void input() {
        max = 0;
        FastReader fr = new FastReader();
        N = fr.nextInt();
        M = fr.nextInt();
        map = new int[N][M];
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = fr.nextInt();
                max = Math.max(max, map[i][j]);
            }
        }
    }

    public static void pro() {
        ans = 0;
        for (int year = 0; year <= 1500; year++) {
            // 빙산 나눠졌는지 확인
            if (check()) {
                ans = year;
                break;
            }

            // 바다 인접부분 녹게하기
            melting();

        }
        System.out.println(ans);

    }

    private static boolean check() {
        int ice = 0;
        queue = new LinkedList<>();
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j] == 0) continue;
                if(visit[i][j]) continue;
                ice++;
                if(ice >= 2) return true;
                queue.add(new int[]{i, j});
                visit[i][j] = true;
                while (!queue.isEmpty()) {
                    int[] poll = queue.poll();
                    int r = poll[0];
                    int c = poll[1];
                    for (int k = 0; k < 4; k++) {
                        int nr = r + dir[k][0];
                        int nc = c + dir[k][1];
                        if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
                        if(visit[nr][nc]) continue;
                        if(map[nr][nc] == 0) continue;
                        visit[nr][nc] = true;
                        queue.add(new int[]{nr, nc});
                    }
                }
            }
        }
        return false;
    }

    private static void melting() {
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j] != 0) continue;
                if(visit[i][j]) continue;
                for (int k = 0; k < 4; k++) {
                    int nr = i + dir[k][0];
                    int nc = j + dir[k][1];
                    if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
                    if(map[nr][nc] > 0) {
                        map[nr][nc]--;
                        visit[nr][nc] = true;
                    }

                }
            }
        }
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        Double nextDouble() { return Double.parseDouble(next()); }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

제출하고 실패를 많이 겪었는데 그 이유는
1. 동시에 melting이 진행되기 때문에 0이된 빙산은 바다로 치면 안됨
2. 반복횟수를 너무 적게잡아서 0이 출력됨

처음 문제를 봤을 때 안전영역 문제와 거의 비슷한 줄 알았으나 바다의 인접부분이 녹는다는 것이 달랐다. 안전영역과 같이 max값만큼 반복하려하니깐 계속 틀렸다.
BFS 문제는 재밌는 거 같다