[백준] 5014

문제

스타트링크

갈 수 있는 방향이 두 방향만 존재하는 BFS 문제였습니다.

• 왜 BFS인가? : 최단거리를 찾는 문제였기 때문입니다. 한 노드에서 갈 수 있는 한 개의 길을 끝까지 파고드는 DFS와 달리, BFS는 한 노드에서 갈 수 있는 모든 길들을 하나씩 순회하며 진행하기 때문에, 가장 먼저 Goal에 도착하는 루트가 최단거리임을 알 수 있습니다.

• 시간 안에 갈거라는 확신이 있었나요? : 네. 최대 Final 층이 10^6층이고, 최악의 경우더라도 visited 배열의 모든 노드를 다 방문해보는 것으로 끝나기 때문에 10^6이 걸립니다. bfs 안에서 적절하게 처리만 해주고 있다면, 이론상 O(N)의 시간복잡도를 갖습니다.
• 공간복잡도를 초과하진 않았는지? : 안그럴거라 생각했습니다. 256MB로 메모리제한이 넉넉한 편이었기 때문입니다. 파이썬의 데이터타입 별 크기가 정확히 어떻게 되는지는 확신할 수 없었지만, 대략 boolean을 넉넉히 1바이트로 생각하더라도 10^6(MB) 짜리 배열을 256개 만들 수 있는 양이기 때문입니다.

첫 시도 : 시간초과

제가 틀렸던 부분은 어디에서 방문을 기록해야 하는가?의 부분이었습니다. 방문할 노드들을 순서대로 갖고 있는 queue에 넣으면서 동시에 방문 기록까지 해주어야 하는데, 노드를 꺼내는 시점에서 방문 기록을 해주어서 시간초과가 나왔습니다.

BFS에서는 큐를 사용하는 까닭에 선입선출로 노드가 pop되게 됩니다. 최초에 방문 기록을 넣어주던 경우에는, 이에 따라 다음과 같은 순서로 push 이후 pop을 기다리게 됩니다.

1. 큐의 가장 끝단에 push 된다.
2. 앞의 노드들이 모두 pop될 때까지 기다린다.
3. 자신의 차례가 오면 pop된다.

그렇기 때문에, pop될 때 방문기록을 해준다는 것은 (1) pop되기까지 차례를 기다리는 모든 노드들 (2) 자신이 push된 후, pop되기 전까지 들어온 모든 노드들 과의 중복이 허용됩니다. 이에 따라 당연히 시간초과가 발생했던 것이고요.

이러한 알고리즘적 비효율성을 고친 정답 코드는 다음과 같습니다.

정답코드

# 5014

import sys
from collections import deque

Final, Start, Goal, Up, Down = map(int, input().split())

visited = [False]*(Final+1)
moves = [Up, Down*(-1)]

def bfs(start) :
	visited[start]=True
	cnt = 0
	queue = deque([(start,cnt)])
	while queue : # O(N)
		n, cnt = queue.popleft() # O(1)
		# visited[n] = True
		if(n == Goal) :
			return cnt
		for dn in moves : # O(2)
			next = n + dn
			if (next <= Final) and (next > 0) and (visited[next] == False) :
				queue.append((next,cnt+1)) # O(1)
				visited[next] = True
	return "use the stairs"
	
print(bfs(Start))

값의 변동이 없을 것이고, 없어야하기 때문에 tuple을 사용해 deque 리스트에 쭉 넣었습니다. 튜플로 묶이는 것은 현재 노드의 번호(=현재 살펴보는 층수)와 몇 번 움직였는지를 세는 cnt 변수입니다.

새롭게 알게된 점

1. n, cnt = queue.popleft()를 사용해 한 번에 파라미터를 받을 수 있다.
2. 방문 기록을 어디에서 하는 지도 신경써주어야 한다.
3. 파이썬은 리턴값의 데이터타입이 달라도 상관없다! (n==Goal인 경우에는 Integer인 cnt를, while을 모두 돌았으나 Goal을 찾지 못한 경우에는 str을 반환해주고 있다.)

개인적으로 예쁘게 짜진 코드라고 생각합니다. 저기에서 조금 더 이쁘게 하려면, isValidMove 라는 이름의 함수를 만들어서 (next <= Final) and (next>0)의 가독성을 높일 수 있겠으나, 처음에 시간초과가 나면서 함수를 타고 들어가는 시간이라도 없애보려고 풀어 썼던 부분입니다.. ㅋㅋㅋ