(Python) 백준 16234: 인구이동

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

16234번: 인구 이동

 

 

pypy3로는 통과했지만, 시간초과 문제로 python은 통과되지 못했다.

아직 시간초과문제에 많이 취약하다는 것이겠지..

 

 

# Code

from collections import deque
 
def bfs(x, y):
    sumv = 0
    visited = set()
    q = deque()
    q.append((x, y))
    while q:
        node = q.popleft()
        if check[node[0]][node[1]] == 0: continue
        visited.add((node[0], node[1]))
        check[node[0]][node[1]] = 0
        sumv = sumv + city[node[0]][node[1]]
 
        for i in range(4):
            nx, ny = node[0] + dx[i], node[1] + dy[i]
            if not (0 <= nx < N and 0 <= ny < N): continue
            if not (L <= abs(city[node[0]][node[1]] - city[nx][ny]) <= R): continue
            if check[nx][ny] == 0: continue
            q.append((nx, ny))
    return visited, sumv // len(visited)
 
 
if __name__ == '__main__':
    N, L, R = map(int, input().split())
    city = [list(map(int, input().split())) for _ in range(N)]
    cnt = 0
    dx = (0, 1, 0, -1)
    dy = (1, 0, -1, 0)
    check = [[-1]*N for _ in range(N)]
    while True:
        flag = 0
        for x in range(N):
            for y in range(N):
                if check[x][y] == 0: continue
                array, change = bfs(x, y)
                if len(array) > 1:
                    flag = 1
                    for i, j in array:
                        city[i][j] = change
        if flag == 0: break
        for i in range(N):
            for j in range(N):
                check[i][j] = -1
        cnt = cnt + 1
    print(cnt)