접근
이전에 풀었던 미로탐색 등 BFS의 최단경로 방문 특성을 통해 푸는 문제이다. 조금 다른 점은 기존 문제는 좌표를 기준으로 위, 아래, 왼쪽, 오른쪽을 탐색했다면, 이 문제에서는 순간이동하는 2 * x, x + 1, x - 1을 다음 탐색 범위에 넣어주면 된다.
BFS 최단 경로 방문 특성 참고 문제: 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python)
한가지 잊기 쉬운 점은, n = k일때를 고려해야 한다는 점이다.
코드
import sys
n, k = map(int, sys.stdin.readline().split())
location = [-1 for _ in range(100001)]
q = [n]
location[n] = 0
while q:
now = q.pop(0)
next = [now * 2, now + 1, now - 1]
for i in range(3):
if 0 <= next[i] <= 100000 and location[next[i]] == -1:
location[next[i]] = location[now] + 1
q.append(next[i])
if location[k] != -1:
break
print(location[k])
더 생각해 볼 것?
...
코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!
반응형
'코딩 > 백준 (Python)' 카테고리의 다른 글
백준 1707번: 이분 그래프 (Python) (0) | 2021.04.14 |
---|---|
백준 7562번: 나이트의 이동 (Python) (0) | 2021.04.13 |
백준 7569번: 토마토 (Python) (0) | 2021.04.11 |
백준 7576번: 토마토 (Python) (0) | 2021.04.11 |
백준 2178번: 미로 탐색 (Python) (0) | 2021.04.11 |
최근댓글