접근

이전에 풀었던 미로탐색 등 BFS의 최단경로 방문 특성을 통해 푸는 문제이다. 조금 다른 점은 기존 문제는 좌표를 기준으로 위, 아래, 왼쪽, 오른쪽을 탐색했다면, 이 문제에서는 순간이동하는 2 * x, x + 1, x - 1을 다음 탐색 범위에 넣어주면 된다.

BFS 최단 경로 방문 특성 참고 문제: 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python)

 

백준 2178번: 미로 탐색 (Python)

접근 문제 설명과 같이 BFS 알고리즘은 해당 위치까지 최단거리로 이동하는 특성이 있다. 예를 들어 첫 칸인 (0, 0)을 탐색할 때 BFS 알고리즘에 따라 현재칸을 기준으로 위, 아래, 왼쪽, 오른쪽 칸

ca.ramel.be

한가지 잊기 쉬운 점은, 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])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!

반응형
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기