N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.
첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.
인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.
func3 전체 로직
func1 절대값 반환
func2 bfs
인접해 있으면서, 함수 결과가 True인 주위 나라들을 큐와 추가적인 리스트에 넣는다.
큐가 끝나면 나라인구의 합과 조건을 만족했던 리스트를 반환한다.
from collections import deque
#절대값 T/F
def func(x,y) :
if L<=abs(x-y)<=R :
return True
else :
return False
def bfs(r,c) :
#최종 인구 합
res = grid[r][c]
#큐 만들기
q = deque([(r,c)])
#인접 국가 리스트
div_city = [(r,c)]
#방문표시
visited[r][c] = 1
while q :
cr,cc = q.popleft()
#네방향을 돌면서 방문하지 않았고, 절대값 조건에 만족하면 큐에 넣고, 인접 국가 리스트에도 넣고 국가의 합에도 추가
for d in range(4) :
nr = cr + dr[d]
nc = cc + dc[d]
if 0<=nr<N and 0<=nc<N and func(grid[cr][cc],grid[nr][nc]) and not visited[nr][nc] :
visited[nr][nc] = 1
q.append((nr,nc))
res += grid[nr][nc]
div_city.append((nr,nc))
#인접국가 길이와, 국가 합, 인접국가 리스트 리턴
return len(div_city),res,div_city
N,L,R = map(int,input().split())
grid = [list(map(int,input().split())) for _ in range(N)]
dr = [0,1,0,-1]
dc = [1,0,-1,0]
cnt = 0
cnt = 0
while True :
#방문배열
visited = [[0]*N for _ in range(N)]
#추후 인구를 재정렬할 리스트
lst = []
#그리드를 돌면서
for r in range(N) :
for c in range(N) :
#bfs를 돌고 길이,인구합,인접국가리스트 리턴
l,res,d = bfs(r,c)
#길이가 1보다 크면 재정렬 리스트에 포함
if l > 1 :
lst.append((res,d))
#재정렬 리스트가 비어있으면 더이상 움직일 수 없으니까 끝내기
if lst == [] :
break
#재정렬 리스트가 있으면 재정렬 리스트를 돌면서 인구 재조정
for i in range(len(lst)) :
#d = 인구 합 // 국가수
d = lst[i][0]//len(lst[i][1])
for r,c in lst[i][1] :
grid[r][c] = d
#while문 끝날때마다 날짜 하루씩 추가
cnt += 1
print(cnt)