인구 이동

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

bfs구현에는 별로 시간이 걸리지 않았으나 자꾸 채점 80%에서 시간 초과라 나와서 엄청나게 헤맸다. 처음에는 bfs를 비효율적으로 구현한 줄 알았으나 검색해보니 체크할 좌표를 이중 for문으로 넣어주는게 아니라 연합이 일어난 것들을 대상으로 다시 큐에 넣어주어야 했다.... 문제에서 시간 제한 같은 조건을 하나도 주지 않아서 더 해결하기 어려웠던 것 같다. bfs 파라미터를 입력하는 것에서 이렇게 시간복잡도가 차이날 줄은 몰랐다. 아직 실력이 부족하다.

from collections import deque
import sys
input = sys.stdin.readline

N, L, R = map(int, input().split())
A = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
count = 0

for i in range(N):
    A.append(list(map(int, input().split())))
    
def bfs(x, y):
    global visited, A
    total = A[x][y]
    count = 1
    queue = deque([(x, y)])
    visited[x][y] = True
    adj = [(x, y)] #연합 국가들
    while queue:
        current = queue.popleft()
        x = current[0]
        y = current[1]
        for i in range(4):
            if x + dx[i] > N-1 or x + dx[i] < 0 or y + dy[i] > N-1 or y + dy[i] < 0:
                continue
            else:
                if L <= abs(A[x][y] - A[x + dx[i]][y + dy[i]]) <= R and not visited[x + dx[i]][y + dy[i]]:
                    queue.append((x + dx[i], y + dy[i]))
                    visited[x + dx[i]][y + dy[i]] = True
                    adj.append((x + dx[i], y + dy[i]))
                    total += A[x + dx[i]][y + dy[i]]
                    count += 1
    if len(adj) > 1:
        for k in adj:
            A[k[0]][k[1]] = total // count
            q.append((k[0], k[1]))
        return False
    else:
        return True

q = deque()
for i in range(N):
    for j in range(N):
        q.append((i, j))

updated = False

while not updated:
    visited = [[False] * N for i in range(N)]
    updated = True
    
    for k in range(len(q)):
        x, y = q.popleft()
        if not visited[x][y]:
            if not bfs(x, y):
                updated = False
        else:
            continue

    if not updated:
        count += 1


print(count)