[Python](BFS) 백준 16234번 : 인구 이동

---

<접근 방법>

1. 인구이동이 없을 때까지 진행하므로 while True의 무한 반복문 속에서 횟수를 세야겠다.
2. bfs를 통해 연합이 이루어질 수 있는 칸들을 묶고 합산을 칸수로 나눔으로써 인구 수를 재배치시킨다.
   이때, 연합의 수가 자기자신뿐이라 1개라면 재배치 및 인구 이동으로 치지 않도록 유의한다.
3. 인구 이동(flag)이 없다면 break문을 통해 반복문에서 빠져나온다.

슈도코드

from collections import deque
def bfs(x, y, num):
    global flag
    q = deque()
    q.append((x, y))
    union = [(x, y)]	# 연합할 칸들의 정보 리스트
    visited[x][y] = 1
    people_sum = num	# 연합할 칸들의 인구 수 총합
    while q:
        ci, cj = q.popleft()
        for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):	# 상우하좌 탐색
            ni = ci + di
            nj = cj + dj
            # 범위 안, 미방문, 인구 차이가 L과 R 사이라면,
            if 0<=ni<N and 0<=nj<N and not visited[ni][nj] and L<=abs(arr[ni][nj]-arr[ci][cj])<=R:
                q.append((ni, nj, arr[ni][nj]))
                visited[ni][nj] = 1
                union.append((ni, nj))
                people_sum += arr[ni][nj]	# 인구 수 더하기
    if len(union) > 1:	# 연합이 가능하다면
        flag = True	# 인구 이동 상태 True
        for i, j in union:
            arr[i][j] = people_sum//len(union)	# 인구 수 재배치
    return


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

count = 0	# 인구 이동 횟수
while True:
    flag = False
    visited = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                bfs(i, j, arr[i][j])
    if not flag: break	# 인구 이동을 단 한번도 하지 않았다면
    count += 1
print(count)

예제 5번의 결과 도출 과정

이해가 되지 않는 부분이 있으면 질문 주세요. 감사합니다.