[Python] 백준 16234 : 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

풀이 과정

• 각 지점에서 출발해서, 인접하고 현재 지점과의 차이가 l이상 r이하인 곳들을 bfs/dfs를 통해서 다 방문한다.
• 방문이 가능하다는 것은 하나의 연합이 된다는 것을 의미한다. 
• visted는 전체 출발에 대해서 하나만 정의해서 쓰면 된다.

전체 코드

move = [(0,1), (1,0), (-1,0), (0,-1)]
def dfs(i, j):
    now = []
    total = 0
    cnt = 0
    queue = [(i, j)]
    while queue:
        x, y = queue.pop()
        if visited[x][y]: continue
        visited[x][y] = True
        now.append((x,y))
        total += A[x][y]
        cnt += 1
        for k, t in move:
            cx = x + k
            cy = y + t
            if 0 <= cx < n and 0 <= cy < n and l <= abs(A[x][y] - A[cx][cy]) <= r:
                queue.append((cx, cy))
    if cnt == 1: return False
    for x, y in now:
        A[x][y] = total//cnt
    return (total, cnt, now)

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

answer = 0
while True:
    visited = [[False] * n for _ in range(n)]
    isTrue = False
    change = []
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                if dfs(i, j):
                    isTrue = True
    if not isTrue: break
    answer += 1
print(answer)