토스트 계란틀(2018 하반기 오전 2번, 백준 16234 인구 이동)

문제 링크: https://www.codetree.ai/frequent-problems/toast-eggmold/description

코드트리

*같은 문제: 백준 16234 - 인구 이동

 

BFS 또는 DFS를 도는데, 조건에 따라서 이동 가능한지 여부를 판단해야 한다. 해당 회차에서 한 번도 계란틀이 열리지 않는다면 그 순간 for문을 탈출하도록 구현했다.

 

여담으로 이 코드를 그대로 백준에 내봤더니 python3으로는 시간초과가, pypy3으로는 통과가 되더라. python3으로 정확히 80%에서 시간초과가 뜨는 경우가 많은 것 같은데... 왜 그런지는 스포일러니까 궁금하다면 아래 접은글을 열어보시길.

 

실제 삼성 코테에서는 어느 조건까지 고려해야 문제가 풀리도록 나왔는지 궁금해진다. 

꼭 python3으로 풀고 싶다면 이 방법을 참고해보자. 백준 기준으로, 연합이 한 번 만들어졌다면 거기에서 탐색을 시작하지 않아도 된다는 아이디어로 연산 오버헤드를 줄일 수 있다고 한다. 실제로 python3 최소 시간으로 푼 사람의 코드도 저런 식으로 구현했더라.

 

 

	def dfs(init_lst):
	y, x = init_lst
	union = []
	stack = [[y,x]]
	visited[y][x] = True
	sum_egg = 0
	while stack:
	cur_y, cur_x = stack.pop()
	sum_egg += field[cur_y][cur_x]
	union.append([cur_y, cur_x])
	for i in range(4):
	next_y, next_x = cur_y+dir[i][0], cur_x+dir[i][1]
	if 0 <= next_y < n and 0 <= next_x < n and not visited[next_y][next_x]: # 방문 가능한데
	if L <= abs(field[cur_y][cur_x]-field[next_y][next_x]) <= R: # 계란틀 여는 조건이면
	visited[next_y][next_x] = True
	stack.append([next_y, next_x])
	end_flag = True
	if len(union) > 1: # 계란틀이 열려있다면
	end_flag = False
	new_egg = sum_egg//len(union)
	for y, x in union: # 평균으로 업데이트
	tmp_field[y][x] = new_egg
	return end_flag
	if __name__ == "__main__":
	n, L, R = map(int, input().split())
	field = [list(map(int, input().split())) for _ in range(n)]
	dir = [[0,1], [1,0], [0,-1], [-1,0]]
	for t in range(2000):
	end_flag = True
	visited = [[0]*n for _ in range(n)]
	tmp_field = [[0]*n for _ in range(n)] # 이번 회차에서 업데이트 된 결과
	for y in range(n):
	for x in range(n):
	if not visited[y][x]:
	end_flag &= dfs([y,x])
	if end_flag: # 더 이상 열 수 있는 계란틀이 없는 경우
	print(t)
	break
	field = tmp_field # 계란틀 업데이트

view raw 토스트 계란틀.py hosted with ❤ by GitHub