[백준] 16234. 인구 이동 - Java

🖇️ 문제 링크

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

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

---

💡 문제 분석

1. N * N크기의 땅을 순회하면서, 4방향으로 인접해있는 나라에 인구 차이가 L명 이상 R명 이하라면 연결되는 양방향 그래프를 만든다.

2. 그래프를 만들고, 모든 땅을 순회하면서 그래프 탐색을 진행하여 연합을 찾은 뒤 인구를 분배한다.

3. 인구 이동이 일어나지 않을 때까지 반복

💡

N = 50이므로 한번 순회에 최대 나라의 수는 2500, 모든 칸을 그래프 탐색 한다고해도 시간은 충분

---

⌨️ 코드

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

public class Q16234 {
    static int n, l, r, ret = 0;
    static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1};
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        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();

        while(true) {
            visited = new boolean[n][n];
            if(bfs())
                ret++;
            else
                break;
        }

        System.out.println(ret);
    }

    public static boolean bfs() {
        boolean chk = false;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(visited[i][j]) continue;
                Queue<Nation> q = new LinkedList<>();
                List<Nation> change = new ArrayList<>();
                q.add(new Nation(i, j));
                change.add(new Nation(i, j));
                visited[i][j] = true;
                int sum = map[i][j];

                while(!q.isEmpty()) {
                    Nation cur = q.poll();
                    for(int d = 0; d < 4; d++) {
                        int ny = cur.y + dy[d];
                        int nx = cur.x + dx[d];
                        if(ny < 0 || nx < 0 || ny >= n || nx >= n || visited[ny][nx]) continue;
                        int dif = Math.abs(map[ny][nx] - map[cur.y][cur.x]);
                        if(l <= dif && dif <= r) {
                            Nation tmp = new Nation(ny, nx);
                            q.add(tmp);
                            change.add(tmp);
                            visited[ny][nx] = true;
                            chk = true;
                            sum += map[ny][nx];
                        }
                    }
                }

                int part = sum / change.size();
                for(Nation n : change)
                    map[n.y][n.x] = part;
            }
        }
        
        return chk;
    }

    static class Nation {
        int y, x;

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

---

⏱️ 결과

Uploaded by Notion2Tistory v1.1.0