[BOJ] 16234. 인구 이동(BFS, 시뮬레이션).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

땅 크기의 범위는 (1 ≤ N ≤ 50)

인구 이동이 발생하는 횟수가 2,000번보다 작거나 같으므로

O(N^2 * 2000) 일 것이다. 

문제에 주어진 시나리오를 살펴보자.

1. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.

-> 인구 차이가 L명 이상, R명 이하일 경우, 다른 나라로 이동하면 되겠다.

-> 이동하면서 연합이 되는 나라 위치와 인구수를 저장해두자.

2. 위의 조건에 의해 열어야 하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.

3. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.

-> 1번 조건에서 이동하니까 2, 3번 조건은 생략해도 되겠다.

4. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.

-> 연합이 생겼다면 저장해둔 나라 위치와 인구수를 활용해서 인구수를 갱신해주자.

5. 연합을 해체하고, 모든 국경선을 닫는다.

-> 이 부분도 생략해버리자~!

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ16234 {
 
    static int N, L, R, map[][];
    static boolean visited[][];
    static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};
    static Queue<Point> q;
    static List<Point> group; 
    
    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];
        group = new LinkedList<>();
        q = new LinkedList<>();
 
        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(process());
    }
 
    private static int process() {
 
        int cnt = 0; // 인구 이동 발생 수
        boolean isMove = false;
        
        while(true) {
 
            visited = new boolean[N][N];
            isMove = false;
            
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    // 이미 확인한 나라 pass
                    if(visited[r][c]) continue;
                    // 연합국을 확인해보자.
                    if(open(r, c)) isMove = true;
                }
            }
            // 연합국이 존재한다면 인구 이동 발생
            if(isMove) cnt++;
            else return cnt;
        }
    }
 
    private static boolean open(int r, int c) {
 
        q.clear();
        group.clear();
        
        q.add(new Point(r, c));
        group.add(new Point(r, c));
        visited[r][c] = true;
        
        int sum = map[r][c];
        // 연합국을 찾으러
        while(!q.isEmpty()) {
            
            Point now = q.poll();
            
            for (int d = 0; d < 4; d++) {
                int rr = now.r + dr[d];
                int cc = now.c + dc[d];
                // 범위를 초과하거나 이미 방문한 국가 pass
                if(rr < 0 || cc < 0 || rr >= N || cc >= N || visited[rr][cc]) continue;
                // 두 나라의 인구 차이가 L명 이상, R명 이하가 아니라면 pass
                int diff = Math.abs(map[now.r][now.c] - map[rr][cc]);
                if(diff < L || diff > R) continue;
                
                // 연합의 인구수와 국가 정보 저장
                sum += map[rr][cc];
                q.add(new Point(rr, cc));
                group.add(new Point(rr, cc));
                visited[rr][cc] = true;
            }
            
        }
 
        // 연합국이 존재하지 않다면
        if(group.size() == 1) return false;
        else {
            // 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)
            int tmp = sum / group.size(); 
            for (Point p : group) {
                map[p.r][p.c] = tmp;
            }
            
            return true;
        }
    }
    
    static class Point {
        int r, c;
 
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
        
    }
}

line 44~60) 인구 이동이 발생하지 않을 때까지 연합국을 확인해보자.

line 68~70) 시작점도 연합국의 일부에 포함

line 74~94) 연합에 포함되는 국가들을 방문해보자.

line 78~92) 4방 탐색

line 88~91) 연합국에 포함되는 국가일 경우,

 인구수 누적, Queue에 추가, 현재 연합에 속한 list에 추가, 방문 처리

line 97~106) 연합국이 존재할 경우 각 국가의 인구수를 갱신