kingsubin

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

public class boj_2573 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M, nx, ny;
    static int[][][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j][0] = Integer.parseInt(st.nextToken());
            }
        }

        int year = 0;

        while (true) {
            int cnt = 0;
            year++;

            // 1년 단위로 빙산 주위에 바다 갯수 체크
            for (int i = 1; i < N-1; i++) {
                for (int j = 1; j < M-1; j++) {
                    if (map[i][j][0] > 0) {
                        cnt++;

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

                            if (map[nx][ny][0] == 0) {
                                map[i][j][1]++;
                            }
                        }
                    }
                }
            }

            // 빙산이 없음 
            if (cnt == 0) {
                System.out.println(0);
                break;
            }

            // 주위의 바다 갯수만큼 빙산 높이 줄이기
            for (int i = 1; i < N-1; i++) {
                for (int j = 1; j < M-1; j++) {
                    if (map[i][j][0] > 0) {
                        map[i][j][0] -= map[i][j][1];
                        map[i][j][1] = 0;
                    }
                    if (map[i][j][0] < 0) map[i][j][0] = 0;
                }
            }

            // 빙산 덩어리 갯수 카운팅
            int ans = 0;
            Stack<int[]> s = new Stack<>();
            boolean[][] v = new boolean[N][M];

            for (int i = 1; i < N-1; i++) {
                for (int j = 1; j < M-1; j++) {
                    if (map[i][j][0] > 0 && !v[i][j]) {
                        v[i][j] = true;
                        s.push(new int[] {i, j});
                        ans++;

                        while(!s.isEmpty()) {
                            int[] now = s.pop();

                            for (int k = 0; k < 4; k++) {
                                nx = now[0] + dx[k];
                                ny = now[1] + dy[k];

                                if (map[nx][ny][0] > 0 && !v[nx][ny]) {
                                    v[nx][ny] = true;
                                    s.push(new int[] {nx, ny});
                                }
                            }
                        }

                    }
                }
            }

            // 덩어리 수가 2개 이상일 경우
            if (ans >= 2) {
                System.out.println(year);
                break;
            }
        }

    }
}

 

- 이제 dfs/bfs에 어느정도 감이 오는것 같다.

- 다른 사람 코드 보니까 내 코드 길이는 거의 2배인거 같다 ..

 

- map을 map[N][M][2] 로 만들어서 마지막 배열쪽에 바다 갯수 카운팅을 저장했다.