[백준 16234번] 인구 이동 :: 늦깎이 IT

[백준 16234번 인구 이동 URL]

우선 문제에서는 조건에 의해 모든 국경선을 연 후에, 그 다음 인구이동을 시작하라고 나와있지만 딱히 순서는

상관이없다.

1) 어느 한 나라와 연합이 될 수 있는 모든 나라를 찾는다.

2) 연합이 될 수 있는 나라들을 모두 찾았으면 인구이동을 시작한다.

3) 인구이동이 끝났으면 다시 1)번을 수행한다.

즉, 다음과 같은 나라들이 있다면 (L=20, R=50)

인구가 50인 나라부터 탐색을 시작해서 연합될 수 있는 나라들을 찾는다.

어느 한 나라로부터(인구 50인 나라) 연합할 수 있는 모든 나라들을 찾았으면 인구이동을 시작한다.

여기서 하나의 연합으로 묶여진 나라들은 방문 여부를 나타내는 2차원 배열에 표시를 해 둔다.

아래와 같이 인구이동이 끝나면, 다시 방문하지 않은 나라부터 탐색을 시작한다. 하지만 아래 그림은 모든 나라를

방문했으므로 한 번의 인구이동이 끝났다고 볼 수 있다.

[코드 분석]

1. while 반복문이 인구이동의 횟수를 나타낸다.

2. map[N][N]을 탐색하면서 방문하지 않은 나라가 있다면, 그 나라부터 시작해서 연합을 찾는다.

3. 인접한 나라가 조건에 부합된다면, union이라는 List에 해당 나라를 저장한다. 여기서 탐색은 Queue를

활용하고, 같은 연합은 List를 활용한다.

4. 조건에 맞는 나라가 더 이상 없다면, while(!q.isEmpty())에 의해서 while문을 벗어나오고 union에 저장된

나라들을 방문하면서 연산(인구 이동)을 해준다.

5. union에 저장된 나라들의 인구 이동이 끝났으면, 방문하지 않은 나라가 없을 때가지 반복한다.

6. 모든 나라를 방문했다면, cnt(인구 이동 횟수)를 증가시켜준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, L, R;
    static int[][] map;
    static int[] dirX = new int[] { 0, 0, 1, -1 };
    static int[] dirY = new int[] { 1, -1, 0, 0 };
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
 
        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];
 
        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());
            }
        }
        System.out.println(solve());
    }
 
    public static int solve() {
 
        int cnt = 0;
        while (true) {
 
            boolean flag = false;
            boolean[][] visited = new boolean[N][N];
 
            for (int i = 0; i < N; i++) {
 
                for (int j = 0; j < N; j++) {
 
                    if (!visited[i][j]) {
                        List<Node> union = bfs(i, j, visited);
                        move(union);
                        if (union.size() > 1)
                            flag = true;
                    }
                }
            }
            if (!flag)
                return cnt;
 
            cnt += 1;
        }
    }
 
    public static List<Node> bfs(int row, int col, boolean[][] visited) {
 
        List<Node> list = new ArrayList<>();
        Queue<Node> q = new LinkedList<>();
        list.add(new Node(row, col, map[row][col]));
        q.offer(new Node(row, col, map[row][col]));
        visited[row][col] = true;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
 
            for (int i = 0; i < 4; i++) {
                int nr = node.row + dirX[i];
                int nc = node.col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc] && isPossible(map[nr][nc], map[node.row][node.col])) {
 
                    q.offer(new Node(nr, nc, map[nr][nc]));
                    list.add(new Node(nr, nc, map[nr][nc]));
                    visited[nr][nc] = true;
                }
            }
        }
        return list;
    }
 
    public static void move(List<Node> list) {
 
        int sum = 0;
        for (Node node : list)
            sum += node.size;
 
        for (Node node : list)
            map[node.row][node.col] = sum / list.size();
    }
 
    public static boolean isPossible(int num1, int num2) {
        int num = Math.abs(num1 - num2);
        return (num >= L) && (num <= R);
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
}
 
class Node {
 
    int row;
    int col;
    int size;
 
    public Node(int row, int col, int size) {
        this.row = row;
        this.col = col;
        this.size = size;
    }
 
}