[백준 1697 / Python] 숨바꼭질

KYUNG HWAN·2021년 8월 25일
0

백준

목록 보기
3/8
post-thumbnail

🧑🏻‍💻 문제링크

문제풀이

BFS 알고리즘으로 풀면 쉽게 풀 수 있는 문제이다. 하지만, 이동할 수 있는 방법이 3가지가 되기 때문에 어떻게 3가지의 방법으로 이동해야 하는지 알아야 되는 문제인 것 같다.

X-1 또는 X+1, 그리고 2*X 는 다음과 같이 나타낼 수 있다.

for next_node in (x-1, x+1, x*2):

코드

from collections import deque

limit = 100001
N, K = map(int, input().split()) # N: 수빈이가 있는 위치, M: 동생이 있는 위치

arr = [0] * limit

def BFS(arr, N, K):
    need_visit = deque()
    need_visit.append(N)    # 수빈이가 있는 현재 위치 추가

    while need_visit:
        node = need_visit.popleft()

        # 동생이 있는 위치면 현재 위치를 반환
        if node == K:
            return (arr[node])

        for i in (node+1, node-1, node*2):
            if (0 <= i < limit) and arr[i] == 0:
                arr[i] = arr[node] + 1
                need_visit.append(i)

print(BFS(arr, N, K))

결과

1697

profile
내가 그린 기린 그림

0개의 댓글