[BOJ] 16234 인구 이동 (java, python)

# 출처 : https://www.acmicpc.net/problem/16234

16234번: 인구 이동

---

# 풀이

예를 들어 입력값이 다음과 같다.

3x3크기(N=3)의 땅이 있으며,

각 나라끼리의 인구수 차이는 5~10 사이(L=5, R=10)일때 연합 국가가 된다.

각 나라의 인구수는 2차원 배열(A)로 주어진다.

3 5 10
10 15 20
20 30 25
40 22 10

---

해당 인구수를 그림으로 표현하면 아래와 같다.

표의 위에를 x 좌표, 왼쪽을 y 좌표로 뒀다.

---

이중 for문을 돌려 전체를 탐색해야한다.

맨 첫번째 (0,0) 부터 탐색을 시작했을때 방문여부 표시를 하고 탐색을 시작한다.

현재 탐색을 시작한 위치(0,0)에 visited[0][0] = true로 변경했다.

---

이때, 맨 처음에 queue에 (0,0) 좌표를 넣은 상태로 시작하며, 

상하좌우로 탐색을 하는 과정에서 연합국가가 되는 좌표는 queue에 넣는다.

상하좌우를 탐색하는 과정에서 배열의 범위를 벗어난 것은 없는지 확인이 필요하다.

---

(0,0) 좌표 탐색이 끝났다면, queue에 남아있는 첫번째 좌표를 poll()로 가져온다.

(1,0)좌표에서 상하좌우를 탐색하되 아까 방문했던 (0,0)은 더이상 탐색하지 않기에 queue에 넣지 않는다.

이렇게 탐색할 좌표들을 queue에 담아가며 연합 국가를 찾는다. 

(1,0) 좌표 탐색 후, (2,0) 좌표가 아닌 (0,1) 좌표를 탐색하는 이유는 큐는 FIFO 구조로 먼저 들어온 데이터를 내보내기 때문이다.

---

최종적으로 아래와 같이 연합국가끼리 인구수를 더하여 연합국가 수 만큼 나눠 분배한 인구수를 집어넣는다.

이 과정을 반복하다보면 더이상 연합국가가 만들어지지 않는 날이 정답 날짜가 된다.

 

코드에서 더이상 연합국가가 만들어지지 않는 날을 판단하는 방법은

이중 for문에서 인구 이동이 한번이라도 일어났는지에 대한 유무를 판단하는 flag를 사용했다.

참고로 다음과 같이 연합국가끼리 인구를 분배한 것을 2차원 배열에 다시 집어넣기 위해, 좌표를 기억할 수 있는 변수를 선언하여 사용하였다.

 

---

# 코드

Java

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    public static boolean isMove = true; // 이동 여부
    public static boolean[][] visited; // 방문 여부
    public static int[][] A; // 인구 수
    public static int N, L, R; // N: 크기, L<= 인구수 차이 <=R : 인구수 차이 L이상 R이하

    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            N=input[0]; L=input[1]; R=input[2];

            A = new int[N][N]; // 인구수가 당긴 2차원 배열
            for(int n=0; n<N; n++){
                A[n] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            }

            int dayCount = 0;
            while(true){
                isMove = false;
                visited = new boolean[N][N]; // 방문 여부 초기화(인구 이동 후, 처음부터 다시 탐색해야하므로) = false로 초기화 시켜줌
                // 2중 for문 탐색 1번 = 하루
                for(int x=0; x<N; x++){
                    for(int y=0; y<N; y++){
                        if(visited[x][y]) continue;
                        BFS(x, y);
                    }
                }
                if(!isMove) break; // 이중 for 문을 돌면서, 한번이라도 인구 이동을 했다면 isMove는 true가 되었을 것이다.
                // 만약 인구 이동이 한 번이라도 하지 못했다면 맨 처음 선언한 isMove=false로 인해 while문은 중단
                dayCount+=1; // 하루가 지나가므로 카운팅
            }

            System.out.println(dayCount);
        } catch(Exception e){
            System.out.println(e);
        }
    }

    public static Point[] UDLR = new Point[]{new Point(-1, 0), new Point(1, 0), new Point(0, -1), new Point(0, 1)}; // 상하좌우
    public static void BFS(int x, int y){
        Deque<Point> q = new ArrayDeque<>(); // 탐색할 좌표
        Deque<Point> position = new ArrayDeque<>(); // 연합 좌표 (추후, 해당 좌표의 인구수를 변경해야하므로)

        // [1] 연합 국가 구하기
        visited[x][y] = true; // 방문했다고 표기
        q.offer(new Point(x, y)); // 처음 좌표 큐에 넣기
        position.offer(new Point(x, y)); // 연합 좌표 넣기
        int totalPeople = A[x][y]; // 연합 인구 수 (이동할 전체 인구 수)
        while(!q.isEmpty()){
            Point xy = q.poll(); // 여기서 계속 빼냄
            for(Point point : UDLR){
                int newX = xy.getX() + point.getX();
                int newY = xy.getY() + point.getY();

                if(newX < 0 || newY < 0 || newX >= N || newY >= N) continue; // 범위 넘어가면, 패스
                if(visited[newX][newY]) continue; // 방문했다면, 패스
                int diffPeople = Math.abs(A[xy.getX()][xy.getY()] - A[newX][newY]);
                if(diffPeople < L || diffPeople > R) continue; // 인구수 차이 범위 안이 아니라면, 패스

                visited[newX][newY] = true;  // 방문표기
                q.offer(new Point(newX, newY)); // 탐색할 좌표 추가
                position.offer(new Point(newX, newY)); // 연합 좌표 추가
                totalPeople += A[newX][newY]; // 인구수 추가
            }
        }

        // [2] 연합 국가 인구 수 분배하기
        if(position.size() > 1){ // 처음 넣은 좌표보다 더 많으면, 이동할 인구가 있다는 의미
            int division = totalPeople / position.size(); // 분배할 인구 수 = 연합인구수 / 연합국가 수
            while(!position.isEmpty()){ // 연합 좌표 하나씩 꺼내서 분배할 인구수를 넣도록 함
                Point p = position.poll();
                A[p.getX()][p.getY()] = division;
            }
            isMove = true; // 이동했다면, true
        }
    }
}

class Point {
    int x;
    int y;

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

    int getX(){ return this.x; }
    int getY(){ return this.y; }
}

Python

from collections import deque #큐 사용

#상, 하, 좌, 우
dxs=[0, 0, -1, 1]
dys=[1, -1, 0, 0]

def BFS(x, y):
    global N, L, R, A, visited, flag
    q=deque() #큐로 생성
    position=[] #위치 저장

    q.append([x, y]) #큐에 초기 x, y 좌표값 추가
    position=[(x, y)] #초기 x, y 좌표값 등록
    visited[x][y]=True #전체 확인용

    total=A[x][y] #이동할 인구수 합
    while q: #큐가 비어질때까지
        nx, ny = q.popleft() #큐 맨앞에꺼 꺼내기
        for dx, dy in zip(dxs, dys): #상하좌우로 4번 탐색
            nextx, nexty = nx+dx, ny+dy #상하좌우 업데이트
            if nextx<0 or nextx>=N or nexty<0 or nexty>=N or visited[nextx][nexty] \
                or abs(A[nx][ny]-A[nextx][nexty])<L or abs(A[nx][ny]-A[nextx][nexty])>R: continue #범위 벗어나거나 방문했던 곳은 제외
            visited[nextx][nexty]=True #방문 표시
            q.append([nextx, nexty]) #큐 맨뒤에 추가
            position.append((nextx, nexty)) #위치 저장(추후 해당 위치의 인구수를 일괄 수정하기 위해서! 중요)
            total+=A[nextx][nexty] #이동할 인구 수 더하기

    if len(position) > 1: #저장된 위치가 2개 이상이라면,(1개는 초기 x, y 좌표 위치이므로)
        person=int(total/len(position)) #이동할 인구의 총 수에 나라 가짓 수 나누기
        for i, j in position: #position에 저장된 각 나라의 인구 수 변경
            A[i][j]=person #임의 변경
        flag=True #이동 유 표기

def main():
    global N, L, R, A, visited, flag

    N, L, R = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    
    count=0 #이동 횟수 카운팅
    while True:
        flag=False #이동 유무 표기
        visited=[[False]*N for _ in range(N)] #방문 여부 확인용 및 이동 후 초기화(이동 후에는 인구 수가 변경되므로 다시 탐색이 필요한 부분! 중요)
        for i in range(N):
            for j in range(N):
                if visited[i][j] == True: continue #방문한 곳 이라면 탐색할 필요 없음
                BFS(i, j) #초기 x, y좌표에서 가지치기처럼 뻗어나가는 함수
        
        if not flag: #이동 무
            break
        count+=1 #이동 횟수 증가
    print(count) #최종 결과 출력
    
if __name__ =='__main__':
    main()