[Python] 16234. 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

---

 

Point

• 시작점을 기준으로 bfs를 통해 연합국가의 좌표를 탐색하고, 평균을 연산한다. 실제 값 반영은 이동에서 수행한다. 

Tip

• bfs의 세번째 반환값으로 flag를 세워서 인구이동이 필요없는(길이가 1)인 국가를 이동대상에 포함하지 않으므로서 연산량을 대폭 줄인다
• check 이차원 배열을 선언해 한번 연합이 탐지된 국가는 모두 True 표시하여 bfs 연산이 필요없도록 한다    

 

메모리 (제한: 512MB)

173460 KB

시간 (제한: 2초)

4296 ms

결과

100%

import sys
from collections import deque

def bfs(y,x):
    global n,l,r
    queue = deque([[y,x]])
    visited = [[y,x]]
    total = MAP[y][x]
    cnt = 1
    while queue:
        y,x = queue.popleft()
        for dydx in ((-1,0),(0,1),(1,0),(0,-1)):
            ny = y + dydx[0]
            nx = x + dydx[1]
            if 0<=ny<n and 0<=nx<n and [ny,nx] not in visited and l<=abs(MAP[ny][nx]-MAP[y][x])<=r:
                visited.append([ny,nx])
                queue.append([ny,nx])
                total += MAP[ny][nx]
                cnt += 1
    avg = total // cnt
    if len(visited) == 1:
        return avg, visited, False
    return avg, visited, True

input = sys.stdin.readline
n,l,r = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(n)]
answer = 0

while True:
    # 연합 찾기
    check = [[False]*n for _ in range(n)]
    union = deque()
    for y in range(n):
        for x in range(n):
            if not check[y][x]:
                avg, visited, flag = bfs(y,x)
                if flag:
                    union.append([avg, visited])
                for v in visited:
                    check[v[0]][v[1]] = True
    # 이동
    for i in range(len(union)):
        for j in union[i][1]:
            MAP[j[0]][j[1]] = union[i][0]
    if not union:
        break
    answer += 1

print(answer)

 

문제를 푸는데 도움이 된 테스트 케이스