[백준_16234] 인구이동 python

시뮬레이팅과 bfs를 적절히 사용하여 해결해야 한다.

# n, l, r 입력
n, l, r = map(int, input().split())

# world 입력
world = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 함수돌

# in_range(x, y)
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < n

# bfs
def bfs():

    global world, visited
    
    # 연합된 나라들의 좌표를 담아 줄 리스트
    union_pos = []

    # 연합된 나라들의 인구수 합 측정용
    union_population = 0

    while q:
        x, y = q.popleft()
        # 연합된 나라들 좌표 넣어주기
        union_pos.append((x, y))
        # 연합된 나라들 인구수 측정해주기
        union_population += world[x][y]

        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            # 주변 나라의 국경이 열릴 수 있으면,
            if in_range(nx, ny) and l <= abs(world[x][y] - world[nx][ny]) <= r and not visited[nx][ny]:
                # 방문 처리 해 주고
                visited[nx][ny] = 1
                # 큐에 넣어주기
                q.append((nx, ny))
    
    # 새로운 인구수
    new_population = int(union_population / len(union_pos))

    # 인구 이동시켜주기
    for u_x, u_y in union_pos:
        world[u_x][u_y] = new_population

# is_open(x, y)
def is_open(x, y):
    # 상 하 좌 우 중
    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
    for dx, dy in zip(dxs, dys):
        # 주변 영역의 좌표
        nx, ny = x + dx, y + dy
        # 범위 내에 있는 한 곳이라도 그 좌표와 값과 현재 값의 차가 l이상 r이하라면
        if in_range(nx, ny) and l <= abs(world[nx][ny] - world[x][y]) <= r:
            return True
    # 다 돌았는데도, 차가 l이상 r이하인적이 없으면 실패
    return False
        

# all_done()
def all_done():
    # world를 돌면서
    for i in range(n):
        for j in range(n):
            # 하나라도 주변에 경계선이 열리면,
            if is_open(i, j):
                # 실패
                return False
    # 다 돌았는데도 경계선이 열린 적이 없으면 성공
    return True

# 설계
# 큐 사용준비
from collections import deque
q = deque()

# ans 설정
ans = 0

while True:
    
    # 만약 인구 이동이 일어나지 않는다면(경계선이 하나도 열리지 않는다면)
    if all_done():
        # 정답 출력하고,
        print(ans)
        # 반복종료
        break

    # 인구 이동이 일어난다면 (경계선이 하나라도 열린다면)
    else:
        # 이동 횟수 증가
        ans += 1
        
        # visited 배열 선언 및 초기화
        visited = [
            [0] * n
            for _ in range(n)
        ]

        # world 돌면서
        for i in range(n):
            for j in range(n):
                # 방문하지 않은 곳을 발견하면,
                if not visited[i][j]:
                    # 방문 처리 해 주고,
                    visited[i][j] = 1
                    # 그 좌표를 큐에 넣어주고
                    q.append((i, j))
                    # bfs 돌려주기
                    bfs()