[Python] 백준 16234. 인구 이동

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

16234번: 인구 이동

삼성SW역량테스트 기출문제. 

 

조건대로 코드를 만들었는데, Python으로는 78%에서 시간초과가 뜨고 PyPy3으로 실행하면 통과한다.

 

Python으로도 통과하려면 코드를 어디서 더 효율화할 수 있을까..?

 

 

	from collections import deque
	import sys
	from copy import deepcopy
	n, l, r = map(int, sys.stdin.readline().split())
	maps = []
	for _ in range(n):
	maps.append(list(map(int, sys.stdin.readline().split())))
	dirs = [(0,1),(0,-1),(1,0),(-1,0)]
	def bfs(maps, start, visited):
	# 조건을 충족하는 좌표들을 group에 저장한다.
	group = set()
	queue = deque()
	queue.append(start)
	while queue:
	y, x = queue.popleft()
	visited[y][x] = 1
	for dy, dx in dirs:
	ny, nx = y+dy, x+dx
	if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]) and not visited[ny][nx] and l<= abs(maps[y][x] - maps[ny][nx]) <= r:
	visited[ny][nx] = 1
	# 조건을 충족하면 group에 좌표를 업데이트한다.
	group.update([(y,x),(ny,nx)])
	queue.append((ny, nx))
	return group
	cnt = 0
	while True:
	# maps 좌표 값이 변하는지 아닌지 확인하기 위해
	prev_maps = deepcopy(maps)
	# 방문 여부를 확인하는 좌표
	visited = [[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
	# bfs로 순회하면서 조건에 맞는 그룹을 저장하는 리스트
	groups = []
	for y in range(len(maps)):
	for x in range(len(maps[0])):
	if visited[y][x] == 0:
	groups.append(bfs(maps, (y,x), visited))
	for each in groups:
	# 그룹이 있으면 len(each)가 0보다 크다.
	if each:
	# 업데이트할 새 값 계산
	value = int(sum([maps[y][x] for y, x in each]) / len(each))
	for y, x in each:
	# maps 값 업데이트
	maps[y][x] = value
	# 이전 맵과 새 맵이 동일하면 더 이상 반복할 필요가 없다.
	if prev_maps == maps:
	break
	cnt += 1
	print(cnt)

view raw [백준] 인구이동.py hosted with ❤ by GitHub