백준 완전탐색 알고리즘을 풀던 중 되게 신선한 풀이법을 알게되었다.
우선 문제는 다음과 같다.
요약하자면 F층 높이의 건물에서, S층에서 시작하여 G층까지 엘리베이터를 타고 도착할 수 있는 경우의 최소 횟수를 구해야한다. 이 때, 엘리베이터는 U(위), D(아래) 버튼밖에 없으며 이 값 역시 입력값으로 주어진다.
DFS, BFS 문제를 연습하던 나는 쉽지않나 생각했다. 하지만 정답률은 33%였고 나 역시 높은 확률로 실패할 것 같았지만 도전해보았다.
물론 실패했다.
내가 처음 짠 코드는 DFS 방식이었다.
DFS로 풀면 되겠다고 생각한 이유는 "엘리베이터를 굳이 위 아래 계속 뻗어갈 필요가 있을까?" 라는 것이었다. 이런 저런 시도를 해보았으나 결과는 처참했다.
건물의 최고층인 F는 자그마치 1,000,000 이라는 어마어마한 수였고, 최악의 상황에는 1층서 1,000,000층 까지 재귀함수를 1,000,000번 호출해야할 수도 있었다.
항상 최악의 상황까지 생각해보자는 것을 다시 한 번 되새기게 되었다.
그리고 최소 횟수 관련 문제는 웬만하면 BFS!! 라는 걸 간과하지말자!
결국 구글에서 답안을 들쳐보았고 꽤 충격받았다. 내가 보고 제출한 답안은 다음과 같다.
from collections import deque
f, s, g, u, d = map(int, input().split())
count = [0 for _ in range(f+1)]
visited = set()
def bfs(start):
q = deque()
q.append(start)
visited.add(start)
while q:
cur = q.popleft()
if cur == g:
return count[g]
for i in (cur+u, cur-d):
if 0 < i <= f and i not in visited:
visited.add(i)
count[i] = count[cur] + 1
q.append(i)
return 'use the stairs'
print(bfs(s))이 문제와 다른 bfs의 차이점은 while문 안에서 실행되는 for문에 있다.
사실 생각해보면 이 역시 2차원 배열을 순회하는 bfs에서 x, y축을 돌아다니는 것과 비슷하지만 위, 아래 두 갈래로 갈 수 있다는 것은 생각도 못 했다.
기억하자. 탐색문제에서 최소 횟수는 BFS.
