[백준] 16234번 인구 이동 파이썬

NxN크기의 땅.

r행 c열에 있는 나라는 A[r][c]명 거주 중.

하루 동안 더 이상 인구 이동이 없을 때까지 인구이동 지속됨.

<인구 이동 방식>

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

 

- 입력

1줄 : N, L, R (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

2~N줄 : 각 나라의 인구수 -> r행 c열에 주어지는 정수는 A[r][c]의 값 (0 ≤ A[r][c] ≤ 100)

 

- 출력

인구 이동이 발생하는 일수

 

16234번 인구 이동

from collections import deque
n,l,r = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
dx = [-1,0,1,0]
dy = [0,-1,0,1]

#국경선을 열지말지 결정하는 함수
def bfs(x,y,index):
    queue = deque()
    queue.append((x,y))
    summary = graph[x][y]
    count = 1
    unitied = [] #연합국가
    unitied.append((x,y))
    union[x][y] = index
   
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0<=nx<n) and (0<=ny<n) and (union[nx][ny]==-1) :
                if l<=(abs(graph[nx][ny] - graph[x][y]))<=r:
                    queue.append((nx,ny))
                    union[nx][ny] = index
                    #국경선을 열수 있다면 연합에 국가를 추가
                    count += 1
                    summary += graph[nx][ny]
                    unitied.append((nx,ny))
 
    for i,j in unitied:
        graph[i][j] = summary//count #연합국가들의 인구수
    return count

total_count = 0
while True:
    union = [[-1]*n for _ in range(n)]
    index=0
    for i in range(n):
        for j in range(n):
            if union[i][j] == -1:
                bfs(i,j,index) #하루 지나서 이동 종료
                index += 1 
    if index == n*n:
        break
    total_count += 1
print(total_count)

 

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

16234번: 인구 이동

참고 : https://hae-sooo97.tistory.com/47