문제
풀이
세가지 방식으로 풀어볼 수 있을 것같다.
- BFS를이용하여 목표지점에 도달했을 때 그때의 비용을 출력
시작위치에서 BFS로 다음 갈수있는 위치를 큐에 넣어주면서 출력한다.
이때 문제점이 발생하는데 순간이동을 할 경우에는 비용이 안들어서 우선순위 큐로하는
것도 나쁘지 않아보인다.
여기서 생각 할 수 있는 문제점은 BFS의 종료시점이다.
종료시점을 언제로 해야할까?
visit[k]를 더이상 작은 비용으로 초기화 하지못할 때 종료를 해야한다.
그렇다면 그 시점은 어떻게 알 수 있을까?
그니까 visit[k]에 있는 값보다 일단 큐에서 방금꺼낸 녀석의 비용이 크다면
볼 필요가 없을것이다.
그러면 우선순위큐이므로 맨 위의 헤드값의 비용이 visit[k]에 수정된 값보다
작거나 같다면 BFS를 종료해도 될것 같다
2.dp를 이용하여 바텀업 방식으로 찾아내서 출력
dp테이블을 dp[i]가 시작지점에서 i지점까지 갈때의 최소비용을 저장하는 테이블이다.
따라서 점화식을 찾아서 대입해준다.
-> 단순 점화식이 안만들어질 것 같다.
dp[i] = min(dp[i], dp[i-1] + 1, dp[i+1] + 1, dp[i * 2])
이런식으로 성립이 되는 듯 해 보이지만 순차적으로 테이블을 채울 수 없어
바텀업 방식은 구현이 안된다.
그렇다고 선뜻 탑다운 방식을 하기위해서는 난이도도있고 시간 복잡도가 가늠이 안된다.
따라서 2번째 방식으로는 건들여 보지는 않겠다.
3.다익스트라 알고리즘을 이용해서 풀어보기
먼저 생각나는 문제점은 edge에대한 정보를 처음부터 저장할 수 없어보인다.
물론 비용이 1인 걸로 그래프의 정보를 등록할 수 있지만 0초만에 가는경우는
구현하기 쉽지 않을 것같다.
그리고 1번에서 했던 결론을 보면 다익스트라 알고리즘과 유사해보여
1번방식으로만 해결하면 될것 같다.
코드
#input sample
# 5 17
#output sample
# 2
import sys
import heapq
INF = int(1e9)
input = sys.stdin.readline
N, K = map(int, input().split())
visit = [INF] * 100001
def BFS(N, K):
q = []
heapq.heappush(q, (0, N))
visit[N] = 0
while (q):
dis, cur = heapq.heappop(q)
if dis > visit[cur] or dis > visit[K]:
continue
if(cur + 1 <= 100000):
cost = dis + 1
if(cost < visit[cur+1]):
visit[cur+1] = cost
heapq.heappush(q, (cost, cur+1))
if(cur - 1 >= 0):
cost = dis + 1
if(cost < visit[cur-1]):
visit[cur-1] = cost
heapq.heappush(q, (cost, cur-1))
if(cur * 2 <= 100000):
cost = dis
if(cost < visit[cur * 2]):
visit[cur * 2] = cost
heapq.heappush(q, (cost, cur * 2))
BFS(N, K)
print(visit[K])
다른사람들의 코드를 보고난후
heap을 안사용해도 되었던 문제인데 굳이 사용해서 시간만 늘어난 코드였다.
어차피 BFS탐색을 하고 순간이동을 했을때만 우선적으로 큐에 popleft를 이용하면
됐었는데 이런점에서 아직 BFS의 이해도가 부족했던것같고
BFS와 최단경로알고리즘의 차이를 철처히 더 공부해야겠다.
