[백준] 16234 인구 이동 java

문제

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번 보다 작거나 같은 입력만 주어진다.

출력

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

풀이

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, low, upper, ansCnt;
    static int[][] countries, populations, united;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //n, low, upper입력
        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        low = stoi(st.nextToken());
        upper = stoi(st.nextToken());
        countries = new int[n][n];
        populations = new int[n][n];
        united = new int[1251][];
        //n개의 줄에 각 나라의 인구수 입력
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                populations[i][j] = stoi(st.nextToken());
                countries[i][j] = 0;
            }
        }

        //인구 이동 플래그
        boolean flag = true;
        while(flag) {
            flag = false;
            //매 인구이동 마다 정보 저장 테이블들을 새로 업데이트 해주어야 함.
            int lavel = 1;
            for(int[] arr : countries) {
                Arrays.fill(arr, 0);
            }
            for (int i = 0; i < 1251; i++) {
                united[i] = null;
            }

            //연합 생성 로직
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int[] ret = null;
                    //i, j에 해당하는 나라와 국경선을 공유하는 나라 순회
                    //방문하지 않았는가? : 라벨링 안된 나라
                    if(countries[i][j] == 0) {
                        //연합 생성
                        ret = bfs(i, j, lavel);
                    }
                    //하나라도 국경을 해제 했는가?
                    if(ret != null) {
                        //플래그 변경
                        flag = true;
                        //캐시 테이블에 저장
                        united[lavel++] = ret;
                    }
                }
            }

            //인구 이동 로직
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //연합이 있는가?
                    if(countries[i][j] != 0) {
                        //인구 수 변경
                        int idx = countries[i][j];
                        populations[i][j] = united[idx][1] / united[idx][0];
                    }
                }
            }
            //국경선이 하나라도 개방 되었는가?
            if(flag) {
                //일 수 증가
                ansCnt++;
            }
        }

        //답 출력
        System.out.println(ansCnt);
    }

    static int[] bfs(int x, int y, int lavel) {
        //연합을 생성하고 나오는 총 인구 수, 나라의 개수 return 해야함
        int[] ret = new int[2];
        int cnt = 0;
        int total = 0;
        //큐 생성
        Queue<Pair> q = new LinkedList<>();
        //시작 노드 삽입
        q.offer(new Pair(x, y));
        //큐가 빌 때 까지 진행
        while(!q.isEmpty()) {
            //큐에서 꺼냄
            Pair cur = q.poll();
            int curr = populations[cur.x][cur.y];
            //원소와 인접한 노드 순회
            for (int i = 0; i < 4; i++) {
                int nextX = dx[i] + cur.x;
                int nextY = dy[i] + cur.y;

                //갈 수 있는가? : 맵을 벗어나지 않는가?
                if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= n) continue;
                //요건을 충족하는가? : 갭이 조건을 충족하면서 라벨링 되지 않았는가?
                int next = populations[nextX][nextY];
                int gap = Math.abs(curr - next);
                if(gap >= low && gap <= upper && countries[nextX][nextY] == 0) {
                    //조건에 충족한다면 큐에 삽입
                    q.offer(new Pair(nextX, nextY));
                    //라벨링 및 나라의 개수, 총 인구 수 update
                    countries[nextX][nextY] = lavel;
                    cnt++;
                    total += populations[nextX][nextY];
                }
            }
        }

        //연합이 생성 되었는가? : 개방된 나라가 1개 이상
        if(cnt > 0) {
            //결과 return [0] : 나라 개수, [1] : 총 인구 수
            ret[0] = cnt;
            ret[1] = total;
            return ret;
        }
        //아니라면 null return
        return null;
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

class Pair {
    int x;
    int y;

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

 

구현 + bfs 문제이다.

 

모든 나라를 순회하면서 아직 라벨링 되지 않은 나라를 bfs를 통해 라벨링 해준 후 모든 나라를 확인 했다면 각나라 별 캐싱 해놓은 정보를 통해 인구 이동을 해주었다. 

 

풀고 나서 다른 분의 풀이를 보니까 bfs를 할 때 각 좌표들을 List를 통해서 저장해놓고 바로바로 인구 이동 로직을 돌려주어서 나보다 공간복잡도, 시간복잡도 면에서 뛰어났다. 

 

구현 문제는 정말 다다익선이다. 알고리즘 문제는 감을 익혀야 한다면 구현은 양치기가 답이다 !