bfs 알고리즘을 사용해서 풀 수 있는 문제였습니다.
각각의 인접 노드는 x-1, x+2, 2*x로 이동 하는 경우이고, 0-1 너비 우선 탐색이므로, 다익스트라 알고리즘을 사용하지 않고도 bfs만으로 최단 거리를 구할 수 있었습니다.
💡0-1 너비 우선 탐색이란?
그래프 간의 간선의 가중치가 0 또는 1밖에 없는 그래프로, 만약 0과 1이 아닌 다른 수로 가중치가 부여되어 있는 그래프라면, 너비 우선 탐색 만으로 최단거리를 찾을 수 없지만, 0-1 그래프는 너비 우선 탐색으로 최단 거리를 찾을 수 있습니다.
그림과 함께 이해하도록 해봅시다.
그래프는 하나의 노드에서 자식 노드로 3개의 노드를 갖는 트리 형태로 가장 쉽게 표현 할 수 있습니다. 각각 1초라는 가중치를 가지고 있고 말이죠.
예제 입력으로 살펴볼까요?
풀이법은 너비 우선 탐색의 풀이와 같습니다.
dist : 방문한 노드까지 걸린 시간을 저장할 길이 100001 만큼의 배열을 생성합니다.
q : 인접 노드를 넣을 데크를 생성합니다
큐가 빌때까지 큐에서 노드를 꺼내고, 인접노드를 검사해서 큐에 집어 넣습니다.
꺼낸 노드가 동생이 서있는 목표 지점과 동일할 때, 걸린 시간을 출력하고 반복문을 종료합니다.
bfs.py
from collections import deque
N, K = map(int, input().split())
dist = [0]*((10**5) + 1)
def bfs():
q = deque()
q.append(N)
while q:
x = q.popleft()
if x == K:
print(dist[x])
break
else:
for i in (x-1, x+1, x*2):
if 0 <= i <= (10**5) and dist[i] == 0:
dist[i] = dist[x] + 1
q.append(i)
bfs()