BOJ 1697鬼ごっこ

質問する

BOJ 1697鬼ごっこ
シルバーI|白駿1697|Python 3 Python池

アルゴリズム#アルゴリズム#

基本的な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()

結果