[백준] 16234 인구이동 - Java

난이도 골드4의 그래프탐색/구현 문제이다.

처음에 문제를 읽어보고, 생각해낸 풀이 방법은 다음과 같다.

• (0,0) 부터 BFS를 돌린다.
• 기본적인 BFS의 로직의 인접한 노드를 방문하지 않았고, 인접한 노드가 방문 가능한 노드일 경우 큐에 인접노드를 추가하는 부분을 방문하지 않았고, 인접한 땅과의 현재 방문 중인 땅의 인구수 차이가 L보다 크거나 같고 R보다 작거나 같으면 큐에 더해준다.
• 큐에 들어가는 땅의 인구 수를 더해서 큐를 poll한 횟수로 나누어 연합의 평균을 구한다.
• 이차원 배열을 돌면서 방문한 노드(국경이 열린 노드)들의 인구 수를 위에서 구한 평균으로 업데이트한다.

하지만 위 방법으로 구현하면 연합이 (0,0)에서 시작하지 않을 경우의 테스트 케이스를 통과할 수 없다.

그래서 생각한 풀이는 위의 풀이를 최대한 활용하고, main에서 land 이차원 배열을 완전탐색하며 bfs를 시행하는 것이었다.

이 부분에서 구현해내는데 시간이 오래걸렸다.
bfs에 사용되는 Queue 외에 인구 수를 업데이트 할 땅들을 넣어두는 List를 하나 만들어서 bfs를 돌았음에도 list가 비어있으면 더 이상 인구이동을 할 수 없다고 판단하고 결과 값을 반환하도록 구현하였다.

package BOJ;

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


public class sol16234 {

    static int n, l, r;
    static int[][] land;
    static boolean[][] border;
    static int sum, cnt;
    static boolean endCheck;
    static int result = 0;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static ArrayList<Point> list;


    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());

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

        result = 0;

        while (true) {
            endCheck = true;
            border = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (!border[i][j]) {
                        bfs(i, j);
                        if (list.size() > 1) {
                            updateLand(sum, cnt);
                            endCheck = false;
                        }
                    }
                }
            }
            if (endCheck) break;
            result++;
        }


        System.out.println(result);


    }

    public static void bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        list = new ArrayList<>();
        q.add(new Point(x, y));
        list.add(new Point(x, y));

        border[x][y] = true;
        sum = land[x][y];
        cnt = 0;
        while (!q.isEmpty()) {
            Point curr = q.poll();
            cnt++;
            for (int i = 0; i < 4; i++) {
                int newX = curr.x + dx[i];
                int newY = curr.y + dy[i];

                if ((newX >= 0 && newX < n) && (newY >= 0 && newY < n)) {
                    int diff = Math.abs(land[curr.x][curr.y] - land[newX][newY]);
                    if ((diff >= l && diff <= r) && !border[newX][newY]) {
                        sum += land[newX][newY];
                        q.add(new Point(newX, newY));
                        list.add(new Point(newX, newY));
                        border[newX][newY] = true;
                    }
                }
            }
            
        }




    }

    public static void updateLand(int sum, int cnt) {
        int avg = sum / cnt;
        for (Point p : list) {
            land[p.x][p.y] = avg;
        }
    }

    public static class Point {
        int x, y;

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

}

리뷰

처음 생각해낸 풀이법으로 테스트케이스 3까지 해결되어서 자신감이 생겼고 기존의 코드에서 조금만 수정하면 되겠지라는 생각을 가지고 문제를 붙잡고 있느라 시간이 너무 오래걸렸다. 그래도 BFS에 대한 이해도는 조금은 생긴 거 같고, 문제를 많이 풀어봐서 구현에 시간을 줄여야겠다는 생각이 들었다.