파이썬 | 백준 | 16234 | 인구 이동

solution

bfs 이용(Puyo Puyo랑 비슷하게 풀면 됨 li-fo.tistory.com/80)

# 16234, 인구 이동
import sys
from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = 1
    tmp = [[x, y]]
    while q:
        a, b = q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0<=nx<n and 0<=ny<n:
                if L<=abs(po[a][b]-po[nx][ny])<=R and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                    tmp.append([nx, ny])
    if len(tmp) > 1:
        unites.append(tmp)


def move():
    for unite in unites:
        s = 0
        for p in unite:
            s += po[p[0]][p[1]]
        avg = s // len(unite)
        for p in unite:
            po[p[0]][p[1]] = avg


n, L, R = map(int, sys.stdin.readline().split())
po = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

cnt = 0
while True:
    unites = []
    visited = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                bfs(i, j)
    if len(unites) == 0:
        break
    move()
    cnt += 1
print(cnt)

PyPy3로 제출

 

문제 출처 www.acmicpc.net/problem/16234

16234번: 인구 이동