[백준] 16234번 : 인구 이동 Gold4(골드4) - JAVA[자바]

[Gold IV] 인구 이동 - 16234

문제 링크

성능 요약

메모리: 42372 KB, 시간: 280 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션

제출 일자

2024년 2월 11일 22:27:11

문제 설명

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

 

접근 방법

1. 인구 이동을 받고 DFS를 통해 연합이 존재하는지 확인한다. (sum, count 를 갱신하면서)

2. 연합의 개수가 2개이상이라면 평균을 구해서 Write를 한다.(dfs)

3. 만약 덮어쓴적이 한번도 없다면 while문을 빠져나간다.

-> 자세한 내용은 코드 주석으로 대체

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    // 입력값 N,인구의 차이 L,R
    static int N, L, R;
    // 배열 복사값과 원본 값
    static int[][] map, copyMap;
    // 방문 배열 visit, 연합만 확인하는 Union배열
    static boolean[][] visit, union;
    // 합,개수,평균을 저장하는 변수
    static int sum, count, avg;

    // 상,하,좌,우
    static int[] dirX = {-1, 1, 0, 0};
    static int[] dirY = {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());
        map = new int[N][N];
        copyMap = new int[N][N];

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

        int answer = 0;
        while (true) {
            // 원본 복사
            for (int i = 0; i < N; i++) {
                copyMap[i] = Arrays.copyOf(map[i], N);
            }
            // 방문배열과 연합 배열 초기화
            visit = new boolean[N][N];
            union = new boolean[N][N];

            boolean exit = true;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 방문한적 있다면 ( = 연합이라면 ) 이미 로직을 처리했으므로 넘어간다.
                    if (visit[i][j]) continue;

                    // 합과 개수를 0으로 초기화해줌
                    sum = count = 0;

                    // 연합 개수와 합을 갱신하는 로직(복사배열에서)
                    getCountSum(i, j);

                    // 만약 개수가 1개라면 ( 연합이 없음 ) 넘어간다.
                    if (count == 1) {
                        continue;
                    }

                    // 평균을 구한 뒤 while문 빠져나가지 않도록 함
                    avg = sum / count;
                    exit = false;

                    // i,j와 관련된 연합 전부 평균값 덮어쓰기(원본에)
                    writeAvgUnion(i, j);
                }
            }

            // 덮어쓴 적이 없다면 while문 빠져나감
            if (exit) {
                break;
            } else {
                answer++;
            }
        }

        System.out.println(answer);
    }

    // 원본 배열에 평균값을 덮어쓰는 메서드
    private static void writeAvgUnion(int x, int y) {
        // 연합 배열에 방문 처리 및 평균값 덮어쓰기
        union[x][y] = true;
        map[x][y] = avg;

        // 상하좌우 확인
        for (int i = 0; i < 4; i++) {
            int nX = x + dirX[i];
            int nY = y + dirY[i];

            // 배열 범위 안에 있거나 || 해당 연합에 방문했다면 넘어감
            if (!isIn(nX, nY) || union[nX][nY]) {
                continue;
            }

            // 값 차이가 유효하다면 재귀호출( 복사 배열에서 확인해줘야 함, 값이 원본 상태이기 때문에 )
            if (isValid(copyMap[x][y], copyMap[nX][nY])) {
                writeAvgUnion(nX, nY);
            }
        }
    }


    // 복사 배열에서 개수와 합을 받아오는 배열
    private static void getCountSum(int x, int y) {
        visit[x][y] = true;
        count++;
        sum += copyMap[x][y];

        for (int i = 0; i < 4; i++) {
            int nX = x + dirX[i];
            int nY = y + dirY[i];

            // 배열 범위내에 있거나 || 방문한적 있다면 넘어감
            if (!isIn(nX, nY) || visit[nX][nY]) {
                continue;
            }

            // 값 차이가 유효한 범위 내에 있다면 재귀 호출( 복사 배열에서 확인, 값이 수정이 안됐기 때문에)
            if (isValid(copyMap[x][y], copyMap[nX][nY])) {
                getCountSum(nX, nY);
            }
        }
    }

    // 차이가 유효한 범위내에 있는가?
    private static boolean isValid(int a, int b) {
        int gap = Math.abs(a - b);
        return gap >= L && gap <= R;
    }

    // 배열범위내에 있는가?
    private static boolean isIn(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
}