# BOJ 16234 - 인구 이동

## BOJ 16234 - 인구 이동

{% embed url="<https://www.acmicpc.net/problem/16234>" %}

인구 이동이 없을 때까지 인구 이동을 하여서 인구 이동이 몇 번 발생하는지 구하라는 문제입니다.

이 문제는 두 나라의 인구 차이가 L명 이상 R명 이하면 국경선을 열어서 같은 인구수로 합치기 때문에 플러드 필 알고리즘이 필요한 문제입니다.

이 문제는 총 3번의 과정을 통해 풀어보겠습니다.

1. 입력값 받기
2. 플러드 필
3. 출력

### 1. 입력값 받기

```python
n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
```

일단 이렇게 값을 받고, 인구 이동은 인접한 국가를 확인하고 있으므로 상하좌우로 이동해야 합니다. 그래서 dx, dy 배열도 추가합니다.

```python
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
```

### 2. 플러드 필

이제 플러드 필을 하면서 인접한 국가에서 인구 차이가 L 이상 R이하이면 국경선을 열어야 합니다. 그러면 이제 국가들이 하나의 연합을 이루고, 이 연합은 여러 개가 있을 수도 있으니 visit 배열을 만들어서 이미 방문한 국가는 방문하지 않도록 합니다.

그리고 인구 이동을 멈출 때까지 계속 진행해야 하므로 while문을 이용해 무한 루프를 만들어줍니다. 그 안에 flag = False라는 변수를 하나 만들어서 인구 이동을 하면 flag = True로 변경해주고, 인구이동을 하지 않으면 flag문을 이용하여 break문으로 빠져나오게 해주면 됩니다.

```python
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False
```

그리고 이제 플러드 필을 해주면 됩니다. 플러드 필은 큐(BFS), 스택이나 재귀(DFS)를 이용하면 되는데, 저는 큐를 이용해서 만들겠습니다.

그러면 collections.deque를 불러오고, 2중 for문을 돌려서 visit\[x]\[y] = 0인 곳을 찾아 플러드필을 하면 됩니다.

```python
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque()
                q.append((i,j))
                visit[i][j] = 1
                blah blah
```

기본적인 플러드 필에 필요한 변수들은 위와 같고, 이제 인구 이동 문제에 필요한 변수는 국경선을 열어서 인구를 전부 합쳐야 하므로 연합의 위치, 연합의 인구수를 구하는 변수를 추가해야 합니다.

이것은 union = \[] 과 population = 0이라는 변수로 설정하겠습니다.

```python
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                blah blah
```

이제 플러드 필을 시작하면 됩니다.

```python
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                while q:
                    x, y = q.popleft()
                    blah blah
```

여기서 주의할 점은 arr\[nx]\[ny]은 배열 밖으로 나가지 말아야 하고, visit\[nx]\[ny] = 0, abs(arr\[x]\[y] - arr\[nx]\[ny])가 L이상 R이하여야만 연합을 이룰 수 있다는 점입니다.

```python
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and L <= abs(arr[x][y] - arr[nx][ny]) <= R:
                            q.append((nx,ny))
                            visit[nx][ny] = 1
                            union.append((nx,ny))
                            population += arr[nx][ny]
```

이제 플러드 필을 마쳤으면 연합을 이루는 국가들이 다 모였거나, 조건을 맞추지 못하여 국경선을 열지 못한 나라도 있을 겁니다.

그래서 len(union) > 1 일 때만 인구 이동을 해주면 됩니다. 이때 flag = True로 설정해주는 것도 잊지 말고 해야 합니다. 인구 이동은 문제에 나온 것처럼 population // len(union) 값을 arr\[x]\[y]에 넣어주면 됩니다.

```python
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and L <= abs(arr[x][y] - arr[nx][ny]) <= R:
                            q.append((nx,ny))
                            visit[nx][ny] = 1
                            union.append((nx,ny))
                            population += arr[nx][ny]
                if len(union) > 1:
                    flag = True
                    for x, y in union:
                        arr[x][y] = population // len(union)
```

### 3. 출력

이제 마지막으로 출력을 해주면 됩니다. 인구 이동이 몇 번 발생하는지 출력해야 하므로 t = 0이라는 변수를 만들어서 추가해주고, 인구 이동을 못 하면(flag = False) break문을 걸어서 while문을 빠져나오고, 아니라면 t += 1을 해주면 됩니다.

코드가 길어서 코드를 추가한 곳에 주석을 달아두었습니다.

```python
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
t = 0 # 추가

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and L <= abs(arr[x][y] - arr[nx][ny]) <= R:
                            q.append((nx,ny))
                            visit[nx][ny] = 1
                            union.append((nx,ny))
                            population += arr[nx][ny]
                if len(union) > 1:
                    flag = True
                    for x, y in union:
                        arr[x][y] = population // len(union)
    # 추가
    if flag: t += 1
    else: break

print(t)
```