[BOJ] 16234. 인구이동 - Simultaion

[BOJ] 16234. 인구이동 - Simultaion

제출일 : 2019-10-15

문제 풀이 시간 : 2H

난이도 : ★★★☆

Problem

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

Input

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

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

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

Output

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

Example

input

2 20 50
50 30
20 40

output

1

Solution & Inpression

시뮬레이션 문제

처음에 문제를 풀땐 국경을 공유할수 있는나라를 다 검사한뒤 connect 배열을 이용하여 체크를 한뒤 연합을 구성할때 DFS를 이용하여 라벨링을 했었다. 이렇게 문제를 푼다면 테스트 케이스는 맞게 되지만

2 10 50
10 100
50 50

이러한 경우에 2개의 연합이 구성되지만 1개의 연합으로 인식하게 되어 문제를 틀리게 된다.

따라서 아래와 같은 방법으로 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 37,292 kb

실행시간 : 444 ms

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, L, R, num;
    static int[][] map, connect;

    static int[] dr = { 1, -1, 0, 0 };
    static int[] dc = { 0, 0, 1, -1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
        N = sc.nextInt();
        // 두 나라의 인구 차이가 L명 이상, R명 이하라면
        L = sc.nextInt();
        R = sc.nextInt();
        map = new int[N][N];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                map[i][j] = sc.nextInt();

        int ans = 0;
        while (true) {

            connect = new int[N][N];
            num = 1;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (connect[i][j] == 0) {
                        if (DFS(i, j, num))
                            num++;
                    }
                }
            }

            if (num == 1) {
                System.out.println(ans);
                return;
            }

            int[] cnts = new int[num];
            int[] sums = new int[num];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    sums[connect[i][j]] += map[i][j];
                    cnts[connect[i][j]]++;
                }
            }

            for (int i = 1; i < num; i++)
                sums[i] /= cnts[i];

            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    if (connect[i][j] != 0)
                        map[i][j] = sums[connect[i][j]];

            ans++;
        }
    }

    private static boolean DFS(int i, int j, int num) {
        boolean flag = false;
        for (int k = 0; k < 4; k++) {
            int r = i + dr[k];
            int c = j + dc[k];
            if (isRange(r, c) && connect[r][c] == 0) {
                int dif = Math.abs(map[i][j] - map[r][c]);
                if (L <= dif && dif <= R) {
                    connect[r][c] = num;
                    DFS(r, c, num);
                    flag = true;
                }
            }
        }
        if (flag) {
            connect[i][j] = num;
            return true;
        }
        return false;
    }

    private static boolean isRange(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }

}