[Python] 인구 이동 - 백준 (BFS)

해당 글은 백준 16234번 문제 '인구 이동'을 다룬다.

문제

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

설명

모든 나라의 위치에서 상하좌우 국경선을 열 수 있는지 확인해야하므로 BFS/DFS로 문제를 풀어야 한다.

해당 코드는 BFS로 풀었으며, while문의 종료조건으로 각각의 나라가 다른 index를 가진다면

즉, index의 값이 n*n이 되면 break한다.

 

코드

from collections import deque

n, l, r = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))


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

def bfs(x, y, index):
    united = []
    united.append((x, y))
    q = deque()
    q.append((x, y))
    union[x][y] = index
    sum = data[x][y]
    count = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < n and ny >= 0 and ny < n and union[nx][ny] == -1:
                if abs(data[nx][ny]-data[x][y]) >= l and abs(data[nx][ny]-data[x][y]) <= r:
                    q.append((nx, ny))
                    union[nx][ny] = index
                    sum += data[nx][ny]
                    count += 1
                    united.append((nx, ny))
    for i, j in united:
        data[i][j] = sum // count

result = 0
while True:
    union = [[-1]*n for _ in range(n)]
    index = 0
    for i in range(n):
        for j in range(n):
            if union[i][j] == -1:
                bfs(i, j, index)
                index += 1
    if index == n*n:
        break
    result += 1
print(result)