[백준] code.plus(시뮬레이션과 구현,JAVA)16234번, 인구 이동

문제 링크

16234번: 인구 이동

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

 

이 문제에 핵심은

 

1. 국가간 인구수의 차이가 L ≤ n ≤ R 사이이면 국경을 공유합니다. 

2. 열 수 있는 국경 공유 완료 후 인구 이동이 진행됩니다.

3. 국경 공유한 나라들은 모두 동일한 인구수(모든 인구 / 공유한 나라)가 됩니다.

4. 더 이상 인구의 이동이 발생하지 않는 일 수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. BFS로 탐색하여 국경을 공유한 나라를 그룹의 형태로 만듭니다.

 

3. 그룹의 형태에 나라들에게 저장할 인구 수를 구해서 저장합니다.

 

4. 2~3을 반복하여 인구 이동이 이루어지지 않을 때 지금까지 일 수를 결과로 출력합니다.

 

 

 

예제입력 3.

 

1. 입력되는 정보들을 저장합니다.

 

N : 3

L : 5

R : 10

10	15	20
20	30	25
40	22	10

 

Day - 1

2. BFS로 탐색하여 국경을 공유한 나라를 그룹의 형태로 만듭니다.

 

10(1)	15(1)	20(1)
20(1)	30(1)	25(1)
40(2)(인구 이동 X)	22(1)	10(3)(인구 이동 X)

 

 

3. 그룹의 형태에 나라들에게 저장할 인구 수를 구해서 저장합니다.

 

10 + 15 + 20 + 20 + 30 + 25 + 22 = 142 / 7 = 20

20	20	20
20	20	20
40	20	10

 

Day - 2

2. BFS로 탐색하여 국경을 공유한 나라를 그룹의 형태로 만듭니다.

 

20(1)(인구 이동 X)	20(2)(인구 이동 X)	20(3)(인구 이동 X)
20(4)(인구 이동 X)	20(5)(인구 이동 X)	20(6)
40(7)(인구 이동 X)	20(6)	10(6)

 

3. 그룹의 형태에 나라들에게 저장할 인구 수를 구해서 저장합니다.

 

20 + 20 + 10 = 50/3 = 16

20	20	20
20	20	16
40	16	16

 

Day - 3(인구 이동 실패)

2. BFS로 탐색하여 국경을 공유한 나라를 그룹의 형태로 만듭니다.

 

20(1)	20(2)	20(3)
20(4)	20(5)	16(6)
40(7)	16(8)	16(9)

 

4. 2~3을 반복하여 인구 이동이 이루어지지 않을 때 지금까지 일 수를 결과로 출력합니다.

 

더 이상 국경이 공유되지 않아 인구 이동이 이루어지지 않기 때문에

지금까지 지난 2일을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력된 정보에 대하여 나누었습니다.
• 인구 이동이 일어나지 않을 때까지 groundSearch함수를 실행하여 시뮬레이션이 진행되도록 하였습니다.
• 인구 이동이 멈추었을 때 지난 일 수 를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• groundSearch함수는 BFS를 이용해서 나라간 국경을 공유하는 그룹을 만들었습니다.
• groundSearch함수는 BFS탐색 이후 그룹에서 인구 이동을 진행하여 인구의 값들을 변경해줍니다.
• inGround함수에서 BFS탐색에서 이동하려는 칸이 땅에서 벗어나지 않는지 확인하는 함수입니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    //나라의 위치를 표현하는 클래스
    static class position{
        int x, y;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N,L,R, sum, count;
    static int[][] ground;	//인구수 저장 배열
    static int[][] groundIndex;	//나라 그룹 번호 저장 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x 변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y 변경값
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        ground = new int[N][N];
        //입력되는 인구수 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<N;j++)
                ground[i][j] = Integer.parseInt(st.nextToken());
        }
        int days = 0;
        //시뮬레이션 시작!
        while(true){
            int index = 1;
            boolean moveCheck = false;	//인구 이동 일어났는지 확인 변수
            groundIndex = new int[N][N];
            //BFS탐색으로 그룹 분류 및 인구 이동 진행
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(groundIndex[i][j]==0){
                        groundSearch(j, i, index++);
                        if(count!=1)	//인구 이동 발생 시
                            moveCheck = true;
                    }
                }
            }
            if(!moveCheck)	//인구 이동 일어나지 않았을 때 종료
                break;
            days++;	//일 수 증가
        }
        bw.write(days + "");	//인구 이동한 일 수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색으로 그룹을 나눈 뒤 인구 이동을 진행하는 함수
    static void groundSearch(int sx, int sy, int index){
        Queue<position> queue = new LinkedList<>();
        queue.add(new position(sx ,sy));
        groundIndex[sy][sx] = index;
        ArrayList<position> group = new ArrayList<>();	//그룹 위치 저장 리스트
        count = 0;		//그룹의 개수
        sum = ground[sy][sx];	//그룹 인구의 합
        while(!queue.isEmpty()){
            position cur = queue.poll();
            count++;
            group.add(new position(cur.x, cur.y));
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                //인접한 나라들 탐색
                if(inGround(tempX,tempY) && groundIndex[tempY][tempX]==0){
                    int temp = Math.abs(ground[cur.y][cur.x] - ground[tempY][tempX]);
                    if(temp >=L && temp<=R){
                        groundIndex[tempY][tempX] = index;
                        sum += ground[tempY][tempX];
                        queue.add(new position(tempX,tempY));
                    }
                }
            }
        }
        int num = sum / count;		//그룹에 속한 나라들 변경할 인구수 구하기
        for(int i=0;i<group.size();i++)	//인구 이동으로 인구수 변경
            ground[group.get(i).y][group.get(i).x] = num;

    }
    //이동한 공간이 땅에 존재하는 곳인지 확인하는 함수
    static boolean inGround(int x, int y){
        if(x>=0 && y>=0 && x<N && y<N)
            return true;
        return false;
    }
}