문제 링크

접근법

처음에 봤을 때
1. 모든 칸을 돌면서 동시에 visited[][] 갱신하면서, 국경선 열지 판단하는 것
2. 한번 열면 다 합쳐서 sum / N 해서 갱신하는 것
3. 차이가 L~R일 때까지 위 과정을 반복하는 것..
이라고 생각하고 코드를 짰다.

잘못된 점

처음에 코드를 구현했을 때 잘못된 점은

• visited를 한 번만 만들고 끝냈다는 거였다
  👉 이 문제는 하루마다 다시 방문 가능하기 때문에 매 day마다 초기화해야한다.

정리해보자면

1. main에서 모든 칸을 순회한다. 방문하지 않은 칸이라면 isOpen을 통해 bfs 4방향 탐색을 진행한다.
   1-1. isOpen이 true을 반환하면 인구이동이 있었다는 것, false면 없었다는 것이기 때문에 해당 반복문을 종료한다.
2. isOpen에서는 기존에 했었던 bfs 4방향 탐색을 돌리는데 ArrayList<int[]> union = new ArrayList<>();를 선언해서 연합 지역을 관리 및 계산해야한다는 게 핵심이다.
   2-1. 또한 sum을 통해서 국경선이 열렸을 때 해당 좌표의 값을 sum에 계속해서 더해야 한다.
3. 4방향 탐색을 돌리면서 Math.abs()를 통해 차이를 구하고 이 차이가 L 이상 R 이하라면 visited, q, union, sum을 갱신한다.
4. 모든 탐색이 끝났다면 union을 통해 인구 이동을 시키면 된다.
   4-1. 연합이 2 이상이면 avg를 만들어서 모두 평균만큼 인구를 이동시킨다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16234_인구이동_G4 {
    static int N, L, R;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    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());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        arr = new int[N][N];
        visited = new boolean[N][N];

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

        int day = 0;

        while (true) {
            visited = new boolean[N][N];
            boolean moved = false;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {
                        if (isOpen(i, j)) moved = true;
                    }
                }
            }

            if (!moved) break;
            day++;
        }

        System.out.println(day);
    }

    public static boolean isOpen(int x, int y) {
        // 여기선 bfs로 4방향을 탐색해야함
        Queue<int[]> q = new LinkedList<>();
        ArrayList<int[]> union = new ArrayList<>();

        q.add(new int[]{x, y});
        union.add(new int[]{x, y});
        visited[x][y] = true;

        int sum = arr[x][y];

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];

            for (int d = 0; d < 4; d++) {
                int nx = cx + dx[d];
                int ny = cy + dy[d];

                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (visited[nx][ny]) continue;

                int diff = Math.abs(arr[cx][cy] - arr[nx][ny]);
                if (diff >= L && diff <= R) {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                    union.add(new int[]{nx, ny});
                    sum += arr[nx][ny];
                }
            }
        }

        // 연합이 2개 이상이면 인구 이동 발생
        if (union.size() > 1) {
            int avg = sum / union.size();
            for (int[] p : union) {
                arr[p[0]][p[1]] = avg;
            }
            return true;
        }
        return false;
    }
}