[DFS/BFS] BOJ 16234 인구 이동

 

🎈 백준 16234 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

 

❗ 문제의 핵심, 풀이 과정

• 인구 이동은 더 이상 인구 이동이 없을 때까지 지속된다.

=> 인구 이동이 있는지 없는지 체크가 필요하다.

 

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

• 조건을 만족하는 국경선이 모두 열렸다면, 인구 이동을 시작한다

=> 조건이 만족하면 모두 열고 하루 동안 인구 이동은 1번 하는 것이다. 예제5를 보면 6번 이동하지만, 하루에 이동한 것이 한 번이기 때문에 총 3번 이동한 것이다.

=> 하루 동안 모든 나라를 확인한 후 인구 이동이 있는 경우 cnt값을 증가시킨다.

 

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

• 인구 이동이 끝나면, 연합을 해체하고, 모든 국경선을 닫는다.

=> 결성된 연합이 인구 이동을 할 때, 오늘 결성된 다른 연합의 바뀐 인구와 땅을 고려하면 안된다. 따라서 연합인지 체크하는 boolean 리스트를 만들어 주어야 한다.

     - 하루마다 초기화 되어야 함으로 while 안에 선언한다.

     - 한 나라의 인접 나라 중 인구 차이가 L명 이상, R명 이하인 나라가 없으면 그 나라를 하나의 연합이라고 생각한다. 이 하루에는 더이상 이 나라를 고려할 필요가 없다.

=> 연합이 아닌 나라를 bfs하여 조건이 성립하면 연합으로 추가한다.

 

• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 

=> 연합에 추가할때 그 나라의 인구수와 칸을 추가하고, 그 땅의 index를 저장할 land_idx 배열을 만들어 저장한다.

 

* 즉 하루의 연합을 체크하는 union boolean 배열은 두 나라 이상이 연합일 때 그 나라들에 True 값, 혹은 주변 나라가 조건을 만족하지 않아 그 자체를 연합으로 치는 한 나라에 True값을 가진다고 할 수 있다.

* 한 나라를 연합으로 치는 연합의 배열로 생각할 수 있고, 하루에 고려가 끝난 나라를 True로 만드는 배열이라고 생각 할 수 있다.   

 

✅ 전체 코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x, y):
    land_idx = []   # 인구 이동할 땅의 인덱스를 저장하는 리스트
    move = False    # 인구 이동 발생 했는지 체크하는 boolean

    land_idx.append((x, y))
    queue = deque()
    queue.append((x, y))
    union[x][y] = True
    people = A[x][y]    # 연합 인구수
    land = 1            # 연합을 이루고 있는 칸의 개수

    # bfs
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 상하좌우 인접 나라 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            dif = abs(A[x][y] - A[nx][ny])  # 인구 차이 계산
            # 인구 차이가 l과 r 사이고 다른 연합이 아니라면
            if l <= dif <= r and not union[nx][ny]:
                # 연합에 추가
                union[nx][ny] = True
                queue.append((nx, ny))
                people += A[nx][ny]
                land += 1
                land_idx.append((nx, ny))
                move = True #인구 이동 체크

    # 인구 이동이 없는 경우 False 리턴
    if not move:
        return move

    # 연합 인구 이동
    change = people // land
    for x, y in land_idx:
        A[x][y] = change
    # 인구 이동이 있는 경우 True 리턴
    return move

n, l, r = map(int, input().split())
A = [[0] * n for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
    A[i] = list(map(int, input().split()))

cnt = 0     # 인구 이동 횟수
# 더 이상 인구 이동이 없을 때까지 지속한다.
while True:
    flag = True     # 인구 이동이 없는 경우
    union = [[False] * n for _ in range(n)] # 연합, 고려한 나라인지 체크할 리스트

    for i in range(n):
        for j in range(n):
            # 연합이 아닌 경우(고려하지 않은 나라인 경우) bfs진행
            if not union[i][j]:
                if bfs(i, j):
                    flag = False    # 인구 이동 check

    # 하루 동안 인구 이동이 없는 경우 종료
    if flag:
        break
    # 하루 동안 인구 이동이 있는 경우 증가
    else:
        cnt += 1
print(cnt)

 

"하루" 라는 조건이 까다로웠다. 문제의 조건을 꼼꼼히 읽었어야 하는 문제였다.