BOJ 16234 - 인구 이동

풀이

---

인구 이동이 얼마나 일어나는지 알아내야하는 문제이다. 인구 이동은 연합이 생성되었을 때 일어나기 때문에 우선 현재 상황에 맞는 연합을 생성해줘야한다. 이 때 BFS 를 통해 연합이 가능한 도시들을 union 에 묶어준 뒤 해당 변수의 특성에 따라서 연산을 해주면된다.

주어진 2차원 배열에 여러가지 연합이 생성될 가능성이 있기 때문에 모든 좌표에서 연합 생성이 가능한 지를 판단하기 위해 모든 좌표를 돌면서 BFS 를 실행해준다. BFS 를 통해 연합이 생성되었을 경우 연합에 해당되는 도시의 인구수를 수정해준 뒤 아직 방문하지 않았던 도시를 찾고 만약 연합 생성이 가능하다면 위 연산을 반복해준다.

모든 좌표에 대한 탐색이 끝난 후 변한 2차원 배열에서 다시 한 번 인구 이동이 발생할 수 있기 때문에 똑같은 연산을 반복한다. 만약 반복한 연산에서 연합이 하나도 생성되지 않았다면, 반복문을 탈출한 뒤 인구 이동이 일어난 횟수를 출력해주면된다.

소스코드

---

# 인구 이동
 
from collections import deque
import sys
 
input = sys.stdin.readline
 
 
def bfs(i, j):
    q = deque()
    q.append([i, j])
    union = []
    union.append([i, j])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:  # 한번도 간 적이 없으며 범위 내일 때
                if l <= abs(s[x][y] - s[nx][ny]) <= r:  # 두 도시의 차이가 범위 내 일 경우
                    q.append([nx, ny])
                    union.append([nx, ny])  # 연합에 소속되는 도시의 좌표
                    visited[nx][ny] = 1  # 방문 처리
    return union
 
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
 
n, l, r = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
 
while True:
    visited = [[0]*n for _ in range(n)]
    isUnion = False
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                visited[i][j] = 1  # 방문 처리
                union = bfs(i, j)  # 방문한 도시에 대한 BFS 실행
                if len(union) > 1:  # 연합이 생성되었을 경우
                    isUnion = True  # 현재 연합이 있는 상태라고 바꿔줌
                    avg = sum([s[x][y] for x, y in union]) // len(union)
                    for x, y in union:
                        s[x][y] = avg
    if not isUnion:  # 모든 좌표를 돌았음에도 연합이 생성되지 않았다면 반복문 탈출
        break
    cnt += 1  # 모든 좌표를 돈 후 인구이동이 종료되었을 때 +1
 
print(cnt)

References

---

• BOJ 16234 - 인구 이동