[백준] 16234 인구이동 (JAVA)

문제 링크:

16234번: 인구 이동

 

 

문제:

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

 

 

출력:

문제이해:

이 문제는 인접한 두 나라의 인구 차이가 L 이상 R 이하일 경우 국경을 열고, 국경이 열린 나라들을 하나의 연합으로 묶는다.
연합의 인구는 모두 합쳐서 나라 수로 나눈 평균값(소수점 버림) 으로 다시 배분된다.

이 과정을 하루 단위로 반복하며, 더 이상 어떤 국경도 열리지 않을 때 종료된다.
결국 문제에서 구하는 값은 인구 이동이 일어난 날 수이다.

 

마지막 예제 예시로 예를 들어보자.

4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

N=4, L=10, R=50 → 인접한 두 나라의 인구 차이가 10~50 사이면 국경 개방.

 

 

Day 1

조건에 맞는 나라들이 연결되어 큰 연합(13칸)이 생김.
→ 평균 인구 = 660 ÷ 13 = 50

10 100  50  50
50  50  50  50
50  50  50  50
50  50 100  50

 

Day 2

여러 개의 작은 연합이 생김.

• (0,0)=10, (1,0)=50 → 평균 30
• (0,1)=100, (1,1)=50, (0,2)=50 → 평균 66
• (2,2)=50, (3,2)=100, (3,3)=50, (3,1)=50 → 평균 62

30  66  66  50
30  66  50  50
50  50  62  50
50  62  62  62

 

Day 3

• (0,0)=30, (0,1)=66 → 평균 48
• 나머지 12칸이 큰 연합 → 평균 54

48  48  54  54
54  54  54  50
54  54  54  54
54  54  62  54

 

Day 4

더 이상 조건에 맞는 국경이 열리지 않음 → 종료.

 

총 3일 동안 인구 이동이 발생했으므로 정답은 3이다.

 

 

구현방향:

인구 이동 문제는 결국 시뮬레이션을 어떻게 구현하느냐가 핵심이다. 우선 하루라는 단위를 기준으로 생각할 수 있다. 하루가 시작되면 전체 땅을 한 번씩 훑으면서, 아직 방문하지 않은 나라에서부터 인접한 나라들을 살펴본다. 이때 단순히 모든 이웃을 다 보는 것이 아니라, 두 나라의 인구 차이가 L 이상 R 이하인 경우에만 국경이 열리고, 그 경로를 따라갈 수 있다. 이렇게 조건을 만족하며 이어지는 나라들을 하나로 묶으면 그것이 바로 “연합”이 된다.

 

연합을 찾는 과정은 BFS(너비 우선 탐색)를 통해 진행한다. 시작한 나라를 큐에 넣고, 조건을 만족하는 인접 나라를 차례차례 방문하면서 같은 연합에 포함시킨다. 결국 탐색이 끝나면 하나의 연합이 완성되고, 그 안에 들어 있는 나라들의 총 인구와 개수를 계산한다. 이어서 평균값을 구해 연합에 속한 모든 나라의 인구를 동일하게 갱신한다.

 

이 과정을 전체 땅에 대해 반복하면 하루가 끝난다. 만약 이 날 단 한 번도 연합이 만들어지지 않았다면, 더 이상 국경을 열 수 없다는 뜻이므로 시뮬레이션을 종료한다. 반대로 연합이 한 번이라도 만들어졌다면, 인구 이동이 일어난 것이므로 하루를 카운트하고 다음 날로 넘어간다.

 

이 과정을 반복하면서, 인구 이동이 며칠 동안 지속되는지를 구할 수 있다. 결국 구현의 큰 흐름은 “하루마다 전체 탐색 → BFS로 연합 형성 → 인구 평균 재배치 → 이동 여부 확인 → 종료 조건 체크”라는 사이클로 요약할 수 있다.

 

이를 그대로 코드로 구현하면 다음과 같다.

 

 

정답 코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N,L,R;
    static int[][] matrix;
    static boolean[][] visited;
    static int result=0;

    //두개의 땅이 공유가 가능한지 검사하는 메서드
    public static boolean canSharing(int delA, int delB){
        int num=Math.abs(delA-delB);
        if(num>=L && num<=R) return true;
        return false;
    }

    //bfs 탐색
    public static boolean bfs(int x, int y){
        int totalHuman=0; //공유하는 사람 총 합
        int totalLand=0;  // 공유하는 땅 개수

        Queue<int[]> q=new LinkedList<>();
        //공유하는 xy좌표 (중복 방지 위해 set 사용)
        Set<List<Integer>> sharingXY = new HashSet<>();

        visited[x][y]=true;
        q.add(new int[]{x,y});

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int curX = cur[0];
            int curY = cur[1];

            //상
            if (curX > 0 && !visited[curX - 1][curY]) {
                if(canSharing(matrix[curX][curY], matrix[curX - 1][curY])) {
                    visited[curX - 1][curY] = true;
                    q.add(new int[]{curX - 1, curY});
                    sharingXY.add(Arrays.asList(curX, curY));
                    sharingXY.add(Arrays.asList(curX - 1, curY));
                }
            }
            //하
            if (curX + 1 < N && !visited[curX + 1][curY]) {
                if(canSharing(matrix[curX][curY], matrix[curX +1][curY])) {
                    visited[curX + 1][curY] = true;
                    q.add(new int[]{curX + 1, curY});
                    sharingXY.add(Arrays.asList(curX, curY));
                    sharingXY.add(Arrays.asList(curX + 1, curY));
                }
            }
            //좌
            if (curY > 0 && !visited[curX][curY - 1]) {
                if(canSharing(matrix[curX][curY], matrix[curX][curY-1])) {
                    visited[curX][curY - 1] = true;
                    q.add(new int[]{curX, curY - 1});
                    sharingXY.add(Arrays.asList(curX, curY));
                    sharingXY.add(Arrays.asList(curX, curY - 1));
                }
            }
            //우
            if (curY + 1 < N && !visited[curX][curY + 1]) {
                if(canSharing(matrix[curX][curY], matrix[curX][curY+1])) {
                    visited[curX][curY + 1] = true;
                    q.add(new int[]{curX, curY + 1});
                    sharingXY.add(Arrays.asList(curX, curY));
                    sharingXY.add(Arrays.asList(curX, curY + 1));
                }
            }
        }

        //연합하는 땅의 개수와 총 인구수 합 구하기
        totalLand=sharingXY.size();
        if(totalLand<2) return false; //연합 없으면 종료

        for (List<Integer> point : sharingXY) {
            int sx = point.get(0);
            int sy = point.get(1);
            totalHuman+=matrix[sx][sy];
        }

        // 각 평균 인원수로 해당 땅에 배분
        int shareHuman=totalHuman/totalLand;
        for (List<Integer> point : sharingXY) {
            int sx = point.get(0);
            int sy = point.get(1);
            matrix[sx][sy]=shareHuman;
        }

        return true;
    }

    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());

        matrix=new int[N][N];
        for (int i=0; i<N; i++){
            StringTokenizer str= new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                matrix[i][j]=Integer.parseInt(str.nextToken());
            }
        }
        //초기 세팅 끝

        while (true){
            visited=new boolean[N][N]; // 하루마다 초기화
            boolean moved=false;

            //전체 탐색
            for (int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(!visited[i][j]){
                        if(bfs(i, j)) moved=true;
                    }
                }
            }

            if(!moved) break;
            else result++;
        }

        //결과 출력
        System.out.println(result);
    }
}

 

 

마무리하며:

이번 문제를 풀면서 작성자는 처음에 연합이 하나만 생기는 경우만을 고려했었다. 그래서 탐색 과정에서 모든 칸이 하나의 set에 모이는 식으로 코드를 짜다 보니, 실제로는 동시에 여러 연합이 생길 수 있다는 점을 간과했던 것이다. 이 부분을 인지하고 BFS를 통해 각 연합을 개별적으로 처리하도록 수정하니 올바른 결과가 나왔다. 

 

결국 이 문제의 핵심은 연합이 여러 개 생길 수 있다는 상황을 염두에 두는 것이 중요하다.

 

 

감사합니다.