https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
풀이
탐색 : 인접한 칸, 이동
연합 국가 구하기 탐색 -> 인구 수 업데이트
BFS : 연합 국가 탐색 : 이동 -> 제한 조건 만족 -> 방문 표시
인구 수 업데이트 : 더이상 이동 불가 -> 연합 국가 간의 인구 수 구하기 -> 업데이트
이동 횟수 증가 : 인구 수 업데이트 한 번 끝나면 증가
#https://www.acmicpc.net/problem/16234
import sys
sys.setrecursionlimit(100000)
'''
#Maximum recursion depth exceed
이 코드에서 재귀의 깊이는 약 2500이 될 수 있습니다.
하지만 파이썬3에는 기본 재귀 제한이 있고 이게 약 1000회 정도입니다.
파이파이3는 이보다 재귀 제한이 더 높아서 통과되는 것으로 보입니다.
파이썬3로 통과하려면 아래와 같은 코드를 상단에 추가하면 됩니다.
'''
N, L, R = map(int, input().split())
lists = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
cnt = 0
def go(x, y):
for i in range(4):
_x = x + dx[i]
_y = y + dy[i]
if 0 <= _x < N and 0 <= _y < N and visited[_x][_y]:
tmp = abs(lists[x][y] - lists[_x][_y])
if L <= tmp <= R:
visited[_x][_y] = False
combine.append([_x, _y])
go(_x, _y)
while True:
visited = [[True] *N for _ in range(N)]
flag = True
for i in range(N):
for j in range(N):
combine = []
if visited[i][j]:
combine.append([i, j])
visited[i][j] = False
go(i, j)
if len(combine) > 1:
flag = False
avg = int(sum([lists[x][y] for x, y in combine]) // len(combine))
for x, y in combine:
lists[x][y] = avg
if flag:
break
cnt += 1
print(cnt)
