[백준] 16234 파이썬(python) : 인구 이동

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

16234번: 인구 이동

 

 

import sys
from collections import deque
n, l, r = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
def bfs(x, y):
    q = deque()
    tmp = []
    q.append((x, y)) #1
    tmp.append((x, y)) #2
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visit[nx][ny]:
                if l <= abs(graph[nx][ny]-graph[x][y])<=r: #3
                    visit[nx][ny] = True
                    q.append((nx, ny)) #4
                    tmp.append((nx, ny)) #5
    return tmp #6
time = 0
while True:
    visit = [ [False]*(n+1) for _ in range(n+1) ] #7
    flag = 0
    for i in range(n):
        for j in range(n):
            if not visit[i][j]:
                visit[i][j] = True
                country = bfs(i, j) #8
                if len(country) > 1: #9
                    flag = 1 #10
                    num = 0
                    for x, y in country:
                        num += graph[x][y] #11
                    number = num // len(country) #12
                    for x, y in country:
                        graph[x][y] = number #13
    if flag == 0: #14
        break
    time += 1 #15
print(time)

 

#1 : 호출된 위치 q에 삽입

#2 : 리턴할 리스트에 호출된 위치 삽입(국경을 개방한 동맹들의 위치를 tmp에 삽입)

#3 : 상하좌우 위치의 노드와의 절댓값 비교에서 l과 r 사이에 들어올때 방문처리

#4 : q에 삽입

#5 : 동맹 리스트에 삽입

#6 : 동맹을 모은 리스트를 리턴

#7 : 방무처리하는 리스트 초기화

#8 : 조건에 맞는 그래프위의 위치일때 bfs호출

#9 : 동맹 리스트를 반환 받은 country의 길이가 2이상일때 

#10 : flag변수 1로 갱신

#11 : 동맹의 위치를 graph에서 모두 가져와 num변수에 더함

#12 : 동맹의 수 만큼 num변수를 나누기 연산(뒤 소수점은 버린다)

#13 : 새롭게 나눠진 인구를 graph안에 동맹들에게 모두 갱신

#14 : 이중for문으로 bfs(i, j)를 모두 돌리고도 더 이상 동맹을 만들 수 없을때 반복문 탈출

#15 : #14에서 걸리지 않는다면 time +1해서 하루를 넘겨줌