[백준 문제풀이] 얼렁뚱땅 16234번 인구 이동 풀이

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

import sys

#sys.setrecursionlimit(10**7)

n, min_, max_ = map(int,input().split())
array = [list(map(int,input().split())) for i in range(n)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]
visited = [[0] * n for i in range(n)]

def dfs(x,y,num) :
	global sum_
	global pos
	visited[x][y] = num
	sum_+=array[x][y]
	pos.append([x,y])

	for i in range(4) :
		nx = x + dx[i]
		ny = y + dy[i]
		if (0<=nx<n) and (0<=ny<n) :
			if (min_ <= abs(array[x][y]-array[nx][ny]) <= max_) and  (visited[nx][ny] == 0) :
				dfs(nx,ny,num)

howmany = 0
num = 1
while num!=(n*n+1) :
	visited = [[0] * n for i in range(n)]
	num = 1
	for i in range(n) :
		for j in range(n) :
			sum_ = 0
			if visited[i][j] == 0 :
				pos = []
				dfs(i,j,num)
				split_ = int(sum_/len(pos))
				for k in pos :
					array[k[0]][k[1]] = split_
				num += 1

	howmany += 1

print(howmany-1)

 

Python으로 하면 sys.setrecursionlimit(10**7)이 필요하다 -> recursion error 때문에

근데, 80% 정도에서 시간초과가 뜬다

 

그래서 pypy3으로 해보았는데

sys.setrecursionlimit(10**7)가 있으면 메모리 초과가 뜬다

근데 저거 없으면 메모리 초과가 안뜬다

 

아주 굉장히 아슬아슬하게 통과됐다고 할 수 있다. ㅋㅋ

 

pypy3은 시간 측면에서 효율적으로 python3은 메모리 측면에서 효율적인 거 같다