[백준] 1697 숨바꼭질 (python 파이썬)

1697번: 숨바꼭질

---

BFS를 활용한 최소 시간을 구하는 문제.

---

아이디어

현재 위치(x)에서 갈 수 있는 거리는 x - 1, x + 1, x * 2이다.

각 경우마다 if문을 통해 조건을 확인해준다.

 

이전에 방문하지 않은 위치라면 그 위치까지 걸리는 시간들을 BFS방식으로 순회하며 시간을 저장해준다.

---

전체 코드

from collections import deque

N, K = map(int, input().split())

deq = deque()

deq.append(N)
visited = [-1] * 100001
visited[N] = 0

while deq:

    x = deq.popleft()

    if x == K:
        print(visited[x])
        break

    for i in [x - 1, x + 1, x * 2]:
        if 0 <= i <= 100000 and visited[i] == -1:
            visited[i] = visited[x] + 1
            deq.append(i)

---

코드 설명

while deq:

    x = deq.popleft()

    if x == K:
        print(visited[x])
        break

    for i in [x - 1, x + 1, x * 2]:
        if 0 <= i <= 100000 and visited[i] == -1:
            visited[i] = visited[x] + 1
            deq.append(i)

 

주어진 범위(0 ~ 100000)에 있는지 확인하고 방문 유무를 따진다.

방문 가능하면 이전까지 소요된 시간에서 + 1 해준다.

 

목표 위치에 도착하면 최소시간을 출력해준다.

 

BFS이므로 각 위치마다 자동적으로 최소시간이 저장된다.