백준 16234번: 인구 이동 (Python, PyPy3)

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

16234번: 인구 이동

접근

bfs 알고리즘을 이용하여 접근하였고, visited 함수를 통해 인구 이동을 통해 변경된 인구로 인한 중복 이동을 제거하였다.

현재 위치에서 동, 서, 남, 북을 탐색한 후, visited 되지 않았으며, 다음 위치와 현재 위치의 값 차이가 L, R 사이라면 다음 위치를 queue에 추가하고, 동맹 목록에 추가해준다. queue 탐색이 끝난 후 동맹 목록의 총 인구수를 동맹 수로 나누어 인구를 배정해준다.

위의 인구 이동을 지도 전체에 진행해 준 후에, 다음 인구 이동을 위해 visited 함수를 초기화해주고 새로 인구 이동을 실시한다.

인구 이동을 진행한 후에도 이전 인구와 같다면 인구 이동을 중단하고 이동 횟수를 프린트해준다.

파이썬으로는 80%에서 시간 초과, PyPy3으로 통과하였다.

코드

from collections import deque

rc = [0, 1, 0, -1]
cc = [1, 0, -1, 0]
N, L, R = map(int, input().split())
matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))


def link(r, c):
    queue = deque([])
    queue.append((r, c))
    visited[r][c] = 1
    linked = [(r, c)]
    sum = matrix[r][c]
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr, nc = r + rc[i], c + cc[i]
            if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == 0:
                if L <= abs(matrix[nr][nc] - matrix[r][c]) <= R:
                    linked.append((nr, nc))
                    queue.append((nr, nc))
                    visited[nr][nc] = 1
                    sum += matrix[nr][nc]
    linked_val = sum // len(linked)
    for i in range(len(linked)):
        matrix[linked[i][0]][linked[i][1]] = linked_val


cnt = 0
while 1:
    visited = [[0] * N for _ in range(N)]
    flag = True
    for i in range(N):
        for j in range(N):
            if visited[i][j] == 1:
                flag = False
                continue
            link(i, j)
    if flag:
        break
    else:
        cnt += 1
print(cnt)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!