[백준] 16234 인구 이동 - JAVA

★★★

문제

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

16234번: 인구 이동

풀이

과정이 길고 복잡해서 그렇지 사실 문제의 설명한 순서대로 구현하면 되는 문제였다.

일단 구현을 시작하기 전에 전체적인 순서를 생각해보았다.

 

1. 방문하지 않은 나라들을 모두 순서대로 탐색한다.

2. 방문 나라를 기준으로 BFS 방식을 사용해 해당 나라와 연합 가능한지 체크한다.

   2-1. 사방탐색으로 기준 나라 인구 수 차이 체크 ( L 이상 R 이하 인지)

   2-2. 연합 가능하다면 연합 리스트에 추가한 후 해당 연합의 인구수합을 따로 저장

3. 더이상 연합 가능한 나라가 없다면 리스트의 나라 인구수를 평균으로 변경한다. (인구 이동)

4. 인구가 이동하지 않았다면 반복문을 멈춘 후 result 값을 반환하거나 이동 하였다면 다시 반복한다.

 

 

반복문 안에 또 탐색 과정을 거쳐야 해서 구현 중 흐름을 잠깐이라도 놓쳤을 때 많이 헷갈려했다..

구현하기 전에 더 자세하게 설계(?) 해야 하는 습관, 또 자세히 주석 적는 습관을 길러야겠다.

코드

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

/*
    인구이동
    골드 5
    시간 : 540ms
    메모리 : 295208kb
*/

public class Main {

    static int N, L, R, result = 0;
    static int[][] A;
    static boolean[][] v;
    static int dr[] = {0, 0, -1, 1};
    static int dc[] = {1, -1, 0, 0};

    public static void main(String[] args) throws Exception {

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

        A = new int[N][N]; //각 나라 인구
        v = new boolean[N][N]; // 방문여부

        // 인구 입력 받기
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        while (true) {
            boolean hasUnion = false; // 연합 존재 여부 확인 변수

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!v[i][j] && findUnion(i, j)) {  //방문한 적 없으면 연합 찾고 연합이 있으면
                        hasUnion = true; // true 변경
                    }
                }
            }

            if (!hasUnion) break; //연합이 없다면 break

            result++;

            // 연합여부 초기화
            for (int i = 0; i < N; i++) {
                Arrays.fill(v[i], false);
            }

        }

        System.out.println(result);
    }

    private static boolean findUnion(int r, int c) {
        Queue<Point> q = new LinkedList<>(); // 방문할 좌표 큐
        List<Point> list = new ArrayList<>(); // 같은 연합 리스트
        int sum = A[r][c]; // 연합 인구수 합계

        v[r][c] = true;
        q.add(new Point(r, c));
        list.add(new Point(r, c));

        // bfs 돌면서 같은 연합인지 확인
        while (!q.isEmpty()) {

            Point cur = q.poll();

            for (int d = 0; d < 4; d++) {
                int nr = cur.r + dr[d];
                int nc = cur.c + dc[d];

                if (!check(nr, nc) || v[nr][nc]) continue;

                int diff = Math.abs(A[cur.r][cur.c] - A[nr][nc]);

                if (diff >= L && diff <= R) { // 연합 가능하다면
                    v[nr][nc] = true;
                    q.add(new Point(nr, nc)); // 큐, 리스트에 좌표 추가
                    list.add(new Point(nr, nc));
                    sum += A[nr][nc]; // 연합 총 인구수 추가
                }
            }
        }

        //연합이 없을 시 f 리턴
        if (list.size() == 1) return false;

        //연합인 나라 인구수 평균으로 초기화
        for (Point p : list) {
            A[p.r][p.c] = sum / list.size();
        }

        return true;
    }

    private static boolean check(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < N;
    }

    private static class Point {
        int r;
        int c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}