백준 1697번-BFS solution (Python)

BFS 연습 - 다음 노드는 (x-1, x+1, x*2)로 갈 수 있다는 점을 파악하면 됨

풀이

from collections import deque
from sys import stdin

input = stdin.readline
N, K = map(int, input().split())
visited = [0 for _ in range(100001)]
    
def BFS(visited, N, K):
    q = deque([N])
    while q:
        x = q.popleft()
        if x == K:
            return visited[x]
        
        for nx in (x-1, x+1, x*2): # 핵심
            if (0 <= nx < 100001) and (visited[nx] == 0):
                visited[nx] = visited[x] + 1
                q.append(nx)

print(BFS(visited, N, K))

처음에 (0 <= nx < 100001) 조건을 안 넣어줘서 인덱스에러 났었음ㅠㅠ 유의하기!

문제 출처: 백준1697번

좋은 웹페이지 즐겨찾기