16234-인구이동

<문제>

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

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]

result = 0
#특정위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
def process(x,y,index):
  #(x,y)와 연결된 나라 정보를 담는 리스트
  united = []
  united.append((x,y))
  #너비 우선 탐색을 위한 큐 자료구조 정의
  q = deque()
  q.append((x,y))
  union[x][y] = index #현재 연합의 번호 할당
  summary = graph[x][y] #현재 연합의 전체 인구수
  count = 1 #현재 연합의 국가 수

  while q:
    x,y = q.popleft()
    #현재 위치에서 4가지 방향 확인
    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:
        #옆에 있는 나라와 인구 차이가 L명 이상, R명 이하라면
        if l<=abs(graph[nx][ny]-graph[x][y])<=r:
          q.append((nx,ny))
          #연합에 추가
          union[nx][ny] = index
          summary += graph[nx][ny]
          count+=1
          united.append((nx,ny))
  #연합국가끼리 인구 분배
  for i, j in united:
    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: #해당 나라가 아직 처리 되지 않았다면
        process(i,j,index)
        index+=1
  if index == n*n:
    break
  total_count+=1

print(total_count)
for i in range(n):
  for j in range(n):
    print(graph[i][j])
    print(union[i][j])