BOJ1697 숨바꼭질

문제

BOJ1697 숨바꼭질
실버I | 백준 1697 | Python3 파이썬 풀이

알고리즘

기본적인 BFS 탐색 알고리즘

코드

import sys
from collections import deque

def BFS():
	# 방문 여부 체크
    visited = [False for i in range(100002)]
    curr = N
    queue = deque()
    queue.append([curr, 0])
	
    # BFS
    while queue:
    	# curr : 지금 위치, sec : 소요 시간
        curr, sec = queue.popleft()
        # print(curr, sec)
		
        # 도착했다면 소요 시간을 출력하고 종료
        if curr == K:
            print(sec)
            return
		
        # 방문 체크
        if visited[curr] == 0:
            visited[curr] = True
			
            # -1
            m1 = curr - 1
            if 0 <= m1 < 100001:
                if not visited[m1]:
                    queue.append([m1, sec + 1])
            
            # +1
            m2 = curr + 1
            if 0 <= m2 < 100001:
                if not visited[m2]:
                    queue.append([m2, sec + 1])
            
            # x2
            m3 = curr * 2
            if 0 <= m3 < 100001:
                if not visited[m3]:
                    queue.append([m3, sec + 1])


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

BFS()

결과