99클럽 코테 스터디 7일차 TIL Boj 1697. 숨바꼭질

Approach

• 최단 경로를 찾는 문제이면서, 간선들의 가중치가 모두 같기 때문에 BFS 탐색이 적합하다고 생각했다.
• 미리 visited 배열을 만들어두고, count를 세가면서 배열을 완성해주었다.

---

Solution 💡

import sys
from collections import deque

def bfs(start, end):

    queue = deque()
    queue.append(start)
    visited[start] = 1
    
    while queue:
        current= queue.popleft()
        
        if current == end:
            return
        
        for i in (current-1, current+1, current*2):
            if 0 <= i <= 100000 and not visited[i]:
                visited[i] = visited[current] + 1
                queue.append(i)
        

N, M = map(int, sys.stdin.readline().split())

visited = [0] * (100001)
bfs(N, M)
print(visited[M] - 1)