문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
내 풀이
from collections import deque
n, k = map(int, input().split())
q = deque()
q.append(n)
visited = [-1 for _ in range(100001)]
visited[n] = 0
while q:
s = q.popleft()
if s == k:
print(visited[s])
break
if 0 <= s-1 < 100001 and visited[s-1]==-1:
visited[s-1] = visited[s] + 1
q.append(s-1)
if 0 < 2*s < 100001 and visited[2*s]==-1:
visited[2*s] = visited[s] + 0
q.appendleft(2*s) # priority
if 0 < s+1 < 100001 and visited[s+1]==-1:
visited[s+1] = visited[s] + 1
q.append(s+1)코멘트
(), (), () 의 3가지 경우로 나누어 탐색해야 된다는 아이디어까지는 닿았는데 에 어떻게 가중치를 줘서 탐색해야할지 구체적으로 생각해내지 못했다.
그래서 다른 풀이를 참고해서 풀이하게 되었는데 BFS를 이용해서 푸는 것이었다. 탐색을 할 때 BFS를 적용해야 하는 경우와 DFS를 적용해야 하는 경우가 구분이 잘 되지 않아서 여기서 한 번 정리하고 넘어가야겠다.
- BFS를 적용하는 경우
- 최단 거리 or 최단 횟수를 구하는 경우
- optimal한 값을 찾는 경우
- 탐색의 횟수를 구해야 하는 경우
- DFS를 적용하는 경우
- 재귀적인 특징과 백트래킹을 활용하여 모든 경우를 전부 탐색하는 경우
- graph의 크기가 클 때
- optimal한 답을 찾는 것이 아닐 경우
- 경로의 특징을 저장해야 하는 경우 (ex) 경로의 가중치, 이동 과정에서의 제약)
이번 문제의 경우에는 최단 시간을 구하는 문제이므로 BFS를 활용하여 풀 수 있다. 우선 방문 여부 및 방문하는데 걸린 최단 시간을 저장할 배열 visited를 무한대 크기로 초기화 해 두고 deque를 활용해 방문하면 방문하면 걸리는 시간을 저장한다. 여기서 포인트는 에 가중치를 주기 위해 q.appendleft를 활용한다는 점이다. 그리고 탐색 범위가 초과되지 않도록 0 < s+1 < 100001 조건을 꼭 넣어주도록 하자.
지금까지의 백준 실버/골드 문제 풀이하는 모습을 회고해 보니 내가 규칙이나 답을 찾는 방법을 알아낸 후에 컴퓨터에게는 그 과정에 따라 계산만 맡기는 식으로 코드를 구현하는 경우가 많았다. 하지만 코딩 테스트는 결국 내가 얼마나 알고리즘을 잘 알고 활용하는지를 테스트하는 것이기 때문에 더 이상 이렇게 풀이하면 안되겠다는 생각을 했다. 알고리즘 공부를 더 부지런히 하고 문제에서 알고리즘을 활용하는 연습을 많이 해야겠다.
References
https://www.acmicpc.net/problem/13549
https://jshong1125.tistory.com/29
https://great-park.tistory.com/19
