백준 16234 인구이동

gmlwlswldbs·2021년 10월 15일
0

코딩테스트

목록 보기
48/130
from collections import deque
n, l, r = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(check, sx, sy, t):
    q = deque()
    q.append((sx, sy))
    check[sx][sy] = t 
    u_pop = g[sx][sy]
    u_num = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if check[nx][ny] == -1 and l <= abs(g[nx][ny]-g[x][y]) <= r:
                u_pop += g[nx][ny]
                u_num += 1
                check[nx][ny] = t
                q.append((nx, ny))
    return check, u_pop, u_num

def move(check, union, g):
    for i in range(n):
        for j in range(n):
            num, pop = union[check[i][j]]
            g[i][j] = pop//num
    return g
ans = 0
while True:
    check = [[-1] * n for _ in range(n)]
    t = 0
    union = []
    for sx in range(n):
        for sy in range(n):
            if check[sx][sy] == -1:
                check, u_pop, u_num = bfs(check, sx, sy, t)
                union.append((u_num, u_pop))
                t += 1 
    if len(union) == 0 or len(union) == n * n:
        break
    g = move(check, union, g)
    ans += 1
print(ans)

0개의 댓글