백준 - 숨바꼭질 3(13549 Python 풀이)

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())

visited = [0 for i in range(10**5 + 1)]
visited[n] = 1
q = deque([n])

while q:
	x = q.popleft()

	if x == k:
		print(visited[x]-1)
		break
		
	for i in (x-1, x+1, x*2):
		if 0 <= i <= 10**5 and not visited[i]:
			if i == x*2:
				visited[i] = visited[x]
				q.appendleft(i)
			else:
				visited[i] = visited[x] + 1
				q.append(i)

최단 거리를 찾는 문제는 BFS 혹은 다익스트라 알고리즘을 통해 풀 수 있는데 둘 중 어떤 알고리즘을 통해 풀어야 하는지 결정하는 요소는 가중치의 여부인 거 같다. 이 문제는 가중치가 0또는 1인 문제이지만 BFS로 푸는게 더 효율적이었고 만약 0 또는 1이 아니라 더 많은 가중치가 있다면 다익스트라 알고리즘을 사용해주어야 한다.

BFS가 시간복잡도 적인 측면에서 BFS가 O(v+E)이고 다익스트라는 O(vlog(E))이기 때문에 BFS로 푸는게 효율적이라서 풀었다.

먼저 방문했는지 안 했는지 여부를 판별해주기 위해 길이가 10**5인 배열을 만들어주었고 반복문을 통해 x-1, x+1, x*2를 모두 할 수 있게 해 최단 경로를 구하는 알고리즘을 찾았고 x*2는 순간이동으로 생각해 0초가 걸리기 때문에 +1을 해주지 않았다.