백준 16234 인구 이동 Python

백준 16234 인구 이동 Python

문제

N × N 크기의 격자 모양의 땅 위에는 각각의 칸마다 하나의 나라가 존재합니다.

각 나라는 자신만의 인구 수를 가지고 있으며, 상하좌우로 인접한 나라와 인구 차이를 비교할 수 있습니다.

두 나라의 인구 차이가 L 이상 R 이하일 경우 두 나라는 국경을 개방합니다.

국경이 열린 나라들은 서로 하나의 연합을 이루며 하루 동안 인구를 자유롭게 이동시킵니다.

연합에 속한 나라들의 인구는 모두 합쳐서 나라의 수로 나눈 평균값으로 재분배됩니다.

이때 소수점은 버림 처리합니다.

하루 동안 모든 연합의 인구 이동이 완료된 후, 다음 날에도 다시 인구 이동이 가능한지 확인합니다.

더 이상 어떤 나라 사이에서도 연합이 생기지 않는 순간 인구 이동이 종료되며,

총 며칠 동안 인구 이동이 발생했는지를 계산하여 출력합니다.

테스트케이스

입력 예제 1

2 20 50
50 30
20 40

출력 예제 1

1

입력 예제 2

2 40 50
50 30
20 40

출력 예제 2

0

입력 예제 3

2 20 50
50 30
30 40

출력 예제 3

1

입력 예제 4

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

출력 예제 4

2

입력 예제 5

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

출력 예제 5

3

문제 작동 원리

🧱 1. 나라들의 격자 구조

입력으로 주어진 숫자들은 N × N 격자 형태로 배치됩니다.

각 칸은 하나의 나라를 의미하며, 그 안의 숫자는 해당 나라의 인구를 나타냅니다.

예를 들어 4×4 격자일 때 다음과 같이 표현됩니다.

┌────┬────┬────┬────┐
│ 10 │100 │ 20 │ 90 │
├────┼────┼────┼────┤
│ 80 │100 │ 60 │ 70 │
├────┼────┼────┼────┤
│ 70 │ 20 │ 30 │ 40 │
├────┼────┼────┼────┤
│ 50 │ 20 │100 │ 10 │
└────┴────┴────┴────┘

이때 각 나라는 상하좌우 네 방향으로 인접한 나라와 인구 차이를 비교합니다.

🔓 2. 국경 개방 조건

두 나라는 반드시 상하좌우로 인접해야 하며,

인구 차이가 L 이상 R 이하일 경우에만 국경을 개방할 수 있습니다.

비교 대상	인구 차이	조건 범위	결과
80 - 100	20	10 ≤ 20 ≤ 50	✅ 국경 개방
10 - 100	90	10 ≤ 90 ≤ 50 ❌	국경 폐쇄

🤝 3. 연합의 형성

국경이 열린 나라들은 서로 연결되어 하나의 연합을 구성합니다.

연합은 반드시 두 나라 이상으로 구성되어야 하며,

연합에 속한 모든 나라의 인구는 평균값으로 다시 분배됩니다.

다음 예시는 일부 나라들이 연합을 이룬 경우를 시각적으로 나타낸 것입니다.

┌────┬────┬────┬────┐
│    │    │(20)│    │
├────┼────┼────┼────┤
│    │    │(60)│(70)│
├────┼────┼────┼────┤
│    │(20)│(30)│(40)│
├────┼────┼────┼────┤
│    │(20)│    │    │
└────┴────┴────┴────┘

괄호로 표시된 부분은 하나의 연합에 속한 나라들을 의미합니다.

🔁 4. 인구 재분배

연합이 형성되면, 해당 연합에 속한 나라들의 인구를 모두 더한 뒤 나라의 개수로 나눈 값을 평균 인구로 계산합니다.

이 평균 인구를 연합에 속한 모든 나라가 동일하게 나누어 가집니다.

예시 계산:

• 연합의 전체 인구: 20 + 60 + 70 + 20 + 30 + 40 = 240
• 연합에 속한 나라의 수: 6개
• 평균 인구: \( 240 \div 6 = 40 \)

따라서 연합 안의 모든 나라의 인구가 40명으로 변경됩니다.

변경된 결과는 아래와 같습니다.

┌────┬────┬────┬────┐
│ 10 │100 │ 40 │ 90 │
├────┼────┼────┼────┤
│ 80 │100 │ 40 │ 40 │
├────┼────┼────┼────┤
│ 70 │ 40 │ 40 │ 40 │
├────┼────┼────┼────┤
│ 50 │ 40 │100 │ 10 │
└────┴────┴────┴────┘

🛑 5. 인구 이동 종료 조건

조건	의미
한 번이라도 연합이 생긴 경우	다음 날 인구 이동을 다시 수행합니다.
아무 연합도 생기지 않은 경우	인구 이동이 완전히 종료되고, 그때까지 걸린 일수를 출력합니다.

아이디어

1. 인접한 나라들 사이의 관계를 탐색해야 하므로 BFS(너비 우선 탐색)를 사용합니다.
2. BFS를 통해 하나의 연합을 구성한 뒤, 그 안의 인구 합과 나라의 개수를 구합니다.
3. 연합의 평균 인구를 계산하여 해당 연합 내의 나라들에 동일하게 분배합니다.
4. 모든 나라를 검사한 뒤, 연합이 하나도 형성되지 않았다면 인구 이동을 멈춥니다.
5. 하나라도 연합이 생겼다면 날짜를 1 증가시키고 다시 과정을 반복합니다.

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

첫째 날 (while 1회) — 집단 결과

형성된 집단(2칸 이상): 하나뿐입니다. (13칸짜리 연합)

규칙에 따라 A만 표시합니다. (다른 칸은 집단 아님이므로 ‘·’)

A만 표시 (집단 포함 vs 미포함)

┌────┬────┬────┬────┐
│ ·  │ ·  │ A  │ A  │
├────┼────┼────┼────┤
│ A  │ A  │ A  │ A  │
├────┼────┼────┼────┤
│ A  │ A  │ A  │ A  │
├────┼────┼────┼────┤
│ A  │ A  │ ·  │ A  │
└────┴────┴────┴────┘

‘·’ 위치(집단 아님, 단독): (0,0)=10, (0,1)=100, (3,2)=100

재분배 결과(하루 끝)

• A(13칸): 합 660 → 660//13 = 50
• ‘·’(단독 3칸): 그대로 10, 100, 100

┌────┬────┬────┬────┐
│ 10 │100 │ 50 │ 50 │
├────┼────┼────┼────┤
│ 50 │ 50 │ 50 │ 50 │
├────┼────┼────┼────┤
│ 50 │ 50 │ 50 │ 50 │
├────┼────┼────┼────┤
│ 50 │ 50 │100 │ 50 │
└────┴────┴────┴────┘

---

둘째 날 (while 2회) — 집단 결과

형성된 집단이 여러 개입니다.

규칙에 따라 A만 표시 → A+B 표시만 보여드립니다. (C 이후는 표기하지 않음)

A만 표시

• A={(0,0),(1,0)} (2칸 집단)

┌────┬────┬────┬────┐
│ A  │ ·  │ ·  │ ·  │
├────┼────┼────┼────┤
│ A  │ ·  │ ·  │ ·  │
├────┼────┼────┼────┤
│ ·  │ ·  │ ·  │ ·  │
├────┼────┼────┼────┤
│ ·  │ ·  │ ·  │ ·  │
└────┴────┴────┴────┘

A+B 표시

• B={(0,1),(0,2),(1,1)} (3칸 집단) 까지 추가

┌────┬────┬────┬────┐
│ A  │ B  │ B  │ ·  │
├────┼────┼────┼────┤
│ A  │ B  │ ·  │ ·  │
├────┼────┼────┼────┤
│ ·  │ ·  │ ·  │ ·  │
├────┼────┼────┼────┤
│ ·  │ ·  │ ·  │ ·  │
└────┴────┴────┴────┘

재분배 결과(하루 끝)

• A: (10,50) → (10+50)//2 = 30
• B: (100,50,50) → 200//3 = 66
• (표시에 포함하지 않았던 다른 집단 C도 존재하며) C: (100,50,50,50) → 250//4=62
• 나머지 ‘·’(단독)은 유지

┌────┬────┬────┬────┐
│ 30 │ 66 │ 66 │ 50 │
├────┼────┼────┼────┤
│ 30 │ 66 │ 50 │ 50 │
├────┼────┼────┼────┤
│ 50 │ 50 │ 62 │ 50 │
├────┼────┼────┼────┤
│ 50 │ 62 │ 62 │ 62 │
└────┴────┴────┴────┘

---

셋째 날 (while 3회) — 집단 결과

형성된 집단이 여러 개입니다.

규칙대로 A만 → A+B만 표시합니다.

A만 표시

• A={(0,0),(0,1)} (2칸 집단)

┌────┬────┬────┬────┐
│ A  │ A  │ ·  │ ·  │
├────┼────┼────┼────┤
│ ·  │ ·  │ ·  │ ·  │
├────┼────┼────┼────┤
│ ·  │ ·  │ ·  │ ·  │
├────┼────┼────┼────┤
│ ·  │ ·  │ ·  │ ·  │
└────┴────┴────┴────┘

A+B 표시

• B=대형 집단(12칸) 추가

┌────┬────┬────┬────┐
│ A  │ A  │ B  │ B  │
├────┼────┼────┼────┤
│ B  │ B  │ B  │ ·  │
├────┼────┼────┼────┤
│ B  │ B  │ B  │ B  │
├────┼────┼────┼────┤
│ B  │ B  │ ·  │ B  │
└────┴────┴────┴────┘

‘·’(단독): (1,3)=50, (3,2)=62

재분배 결과(하루 끝)

• A: (30,66) → 48
• B: 합 648, 12칸 → 54
• 단독 ‘·’: 그대로 (1,3)=50, (3,2)=62

┌────┬────┬────┬────┐
│ 48 │ 48 │ 54 │ 54 │
├────┼────┼────┼────┤
│ 54 │ 54 │ 54 │ 50 │
├────┼────┼────┼────┤
│ 54 │ 54 │ 54 │ 54 │
├────┼────┼────┼────┤
│ 54 │ 54 │ 62 │ 54 │
└────┴────┴────┴────┘

---

넷째 날 (while 4회) — 종료

인접 차이가 모두 10 미만이어서 집단(2칸 이상) 형성 없음 → 인구 이동 종료.

총 발생 일수: 3.

---

코드

from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = 0

N, L, R = map(int, input().split())
arr = []

for _ in range(N):
    k = input().split()
    arr2 = []
    for i in k:
        arr2.append(int(i))
    arr.append(arr2)

q = deque()

while True:
    no_search = True
    check = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if check[i][j] == 1:
                continue
            if check[i][j] == 0:
                check[i][j] = 1
                q.append([i, j])
                cnt_temp = 1
                sum_temp = arr[i][j]
                visited = [[i, j]]

                while q:
                    x, y = q.popleft()
                    for a, b in zip(dx, dy):
                        xx = a + x
                        yy = b + y

                        if 0 <= xx < N and 0 <= yy < N and check[xx][yy] == 0 \
                                and L <= abs(arr[x][y] - arr[xx][yy]) <= R:
                            no_search = False
                            q.append([xx, yy])
                            check[xx][yy] = 1
                            cnt_temp += 1
                            sum_temp += arr[xx][yy]
                            visited.append([xx, yy])

                val = sum_temp // cnt_temp
                for x, y in visited:
                    arr[x][y] = val

    if no_search:
        break
    else:
        cnt += 1

print(cnt)

결론

이 문제는 인구 이동의 반복 시뮬레이션과 연합 탐색(BFS)를 결합한 문제입니다.

핵심은 “인구 차이에 따른 연합의 형성과 평균 인구 재분배”를 매일 반복하면서,

더 이상 변화가 없을 때까지 이를 계속 수행하는 구조를 구현하는 것입니다.

이 과정을 통해 인구 이동이 며칠 동안 발생했는지를 계산할 수 있습니다.