💡 문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
💭 접근
처음 이 문제를 보았을 때 단순 BFS를 사용하여 x + 1과 x - 1로 이동할 때는 +1. x + x로 이동할 때는 +1을 하지 않는 방법으로 탐색을 진행하였다.
그러나 (x + 1, x - 1, x + x)의 순서에 따라 정답 유무가 달라지는 것을 알았고, 반드시 (x + x, x - 1, x + 1) 순서로 탐색을 진행해야 정답이 도출되는 것을 볼 수 있었다.
이에 대해 찾아본 결과, 이러한 풀이는 이 문제에서만 특수하게 맞은 경우이고 일반적인 경우에는 모두 틀려야 한다는 것이다. 따라서 반드시 최적해를 찾을 수 있는 다익스트라 알고리즘을 사용하여 해결하였고, 처음에 떠올렸던 방법과 동일하게 해결하였다.
for nx in (x + 1, x - 1, x + x):
cost = dist
if nx != x + x:
cost += 1
if 0 <= nx < 100001 and cost < distance[nx]:
distance[nx] = cost
heapq.heappush(q, (cost, nx))🔥 처음 풀이
from collections import deque
def bfs():
q = deque()
q.append((n, 0))
while q:
x, cnt = q.popleft()
if x == k:
print(cnt)
return
for nx in (x + x, x - 1, x + 1):
if 0 <= nx < 100001 and visited[nx] == 0:
if nx == x + x:
visited[nx] = cnt
q.append((nx, cnt))
else:
visited[nx] = cnt + 1
q.append((nx, cnt + 1))
n, k = map(int, input().split())
visited = [0 for _ in range(100001)]
bfs()📒 코드
import heapq
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, x = heapq.heappop(q)
if x == k:
print(distance[x])
break
if distance[x] < dist:
continue
for nx in (x + 1, x - 1, x + x):
cost = dist
if nx != x + x:
cost += 1
if 0 <= nx < 100001 and cost < distance[nx]:
distance[nx] = cost
heapq.heappush(q, (cost, nx))
n, k = map(int, input().split())
distance = [1e10 for _ in range(100001)]
dijkstra(n)💭 후기
처음으로 다익스트라 알고리즘을 사용한 문제였다. 다익스트라가 익숙해질때까지 더 연습해야겠다.
🔗 문제 출처
https://www.acmicpc.net/problem/13549
