🥚문제링크

https://www.acmicpc.net/problem/13549

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 너비 우선 탐색
• 다익스트라
• 0-1 너비 우선 탐색

---

🍳코드

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

N, K = map(int, input().split())

visited = [-1]*100001
visited[N] = 0

q = deque([N])
while q:
    x = q.popleft()

    if x == K:
        print(visited[x])
        break

    if 0 <= x * 2 < 100001 and visited[x*2] == -1:
        visited[x*2] = visited[x]
        # 0 - 1 BFS
        # 가중치가 0인 것은 큐의 뒤가 아니라 앞에 넣는다
        q.appendleft(x*2)
    
    if 0 <= x - 1 < 100001 and visited[x-1] == -1:
        visited[x-1] = visited[x] + 1
        q.append(x-1)
    
    if 0 <= x + 1 < 100001 and visited[x+1] == -1:
        visited[x+1] = visited[x] + 1
        q.append(x+1)

---

🧂아이디어

0-1 BFS

참고: https://sihyungyou.github.io/boj-13549/

• 걷는 경우는 1초, 순간이동의 경우 0초로 이동하는 데 소요되는 시간이 다르다 = 간선의 가중치가 다르다
  • 일반 BFS는 가중치가 같은 경우 사용!!

• 0-1 BFS는 가중치가 0인 노드를 큐의 앞으로 push
  • deque의 appendleft를 이용

• 📛 주의
  • (1)방문 체크리스트, (2)최소 시간을 저장하는 리스트 총 2개를 사용하지 않고 나의 코드처럼 리스트 하나를 사용하여 visited[x] == -1이면 방문하지 않은 경우, visited[x] != -1이면 x를 방문하는 최소 시간으로 저장하는 경우라면 순간이동을 하는 x*2부터 검사해야한다!
  • 예를 들어, 입력이 1 2로 주어질 때, 걷는 경우인 x+1를 먼저 검사해주면 visited[1+1]이 더이상 -1이 아니게 되어, 답인 0이 아닌, 1이 출력되게 된다.

• +) dijkstra 를 이용하여 풀이할 수도 있음