[Baekjoon] 16234번: 인구 이동

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

16234번: 인구 이동

문제 설명

BFS를 활용한 구현, 시뮬레이션 문제이다. 문제 조건을 읽고 하나하나 꼼꼼하게 작성해 나가면 된다.

풀이 방법

구현 문제다 보니 코드가 꽤 길다(100줄 가량 된다).

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

class Main {
    static int N, L, R;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] land;
    static boolean[][] isVisited;
    static ArrayList<Coordinate> coordinates;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        L = Integer.parseInt(split[1]);
        R = Integer.parseInt(split[2]);

        land = new int[N][N];
        for (int i = 0; i < N; i++) {
            split = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                land[i][j] = Integer.parseInt(split[j]);
            }
        }

        System.out.print(move());
    }

    private static int move() {
        int result = 0;
        while (true) { // 무한반복하면서 더 이상 이동할 인구가 없으면 종료한다.
            boolean isMoved = false;
            isVisited = new boolean[N][N]; // 반복할 때마다 방문처리 초기화
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!isVisited[i][j]) {
                        int sum = bfs(i, j);
                        if (coordinates.size() > 1) {
                            changePopulation(sum);
                            isMoved = true;
                        }
                    }
                }
            }
            if (!isMoved)
                return result;
            result++;
        }
    }

    private static int bfs(int x, int y) {
        Queue<Coordinate> q = new LinkedList<>();
        coordinates = new ArrayList<>();

        q.offer(new Coordinate(x, y));
        coordinates.add(new Coordinate(x, y));
        isVisited[x][y] = true;

        int sum = land[x][y];
        while (!q.isEmpty()) {
            Coordinate c = q.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = c.x + dx[i];
                int nextY = c.y + dy[i];

                if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N)
                    continue;

                if (isVisited[nextX][nextY])
                    continue;

                int diff = Math.abs(land[c.x][c.y] - land[nextX][nextY]);

                if (L <= diff && diff <= R) {
                    q.offer(new Coordinate(nextX, nextY));
                    coordinates.add(new Coordinate(nextX, nextY));
                    sum += land[nextX][nextY];
                    isVisited[nextX][nextY] = true;
                }
            }
        }

        return sum;
    }

    private static void changePopulation(int sum) {
        int avg = sum / coordinates.size();
        for (Coordinate c : coordinates) {
            land[c.x][c.y] = avg;
        }
    }

    private static class Coordinate {
        int x, y;

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

회고

까다로웠던 점은 반복 처리였다. BFS를 활용한 시뮬레이션 구현 문제는 이번이 처음이었던 것 같은데 코드가 길어지기 시작하니까 내가 내 코드에 빠져서 조건 처리를 하기 헷갈려 시간이 오래 걸렸다. 처음엔 bfs라는 메서드 하나로 다 처리하려고 하다보니 메서드 하나의 코드가 50줄이 넘어가고 그 이후부터는 코드 흐름을 파악하기도 어려웠다. 다음부터 구현 문제를 만나면 메서드를 나누어서 흐름을 보기 좋게 만들어야겠다.