[백준/파이썬]13549번 - 숨바꼭질 3 / BFS

---

접근방법

 

N에서 K로 가는 최단 시간을 구하기 위해서는 N부터 n*2, n-1, n+1에 해당하는 모든점을 계속 접근해가며

시간을 구해야한다고 생각했다.

따라서 BFS를 이용했다

---

풀이

 

크기가 200001인 배열을 만들고 N을 0으로 하여 점을 이동하면서 시간을 계속 갱신하였고

모든 점을 돌았을때 K에 해당하는 시간을 출력하였다.

BFS안에서 시간소요가 없는 x*2와 x-1, x+1은 분기하여 처리하였다

계산한 시간이 더 빨라 값이 갱신되는 경우만 큐에 넣었다

---

정답 코드

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
INF = 200001
line = [INF] * 200001


def bfs():
  q = []
  q.append(n)
  line[n] = 0
  while q:
    x = q.pop(0)
    for nx in (x * 2, x - 1, x + 1):
      if 0 <= nx and nx <= 200000:
        if nx == x * 2:
          if line[nx] > line[x]:
            line[nx] = line[x]
            q.append(nx)
        else:
          if line[nx] > line[x] + 1:
            line[nx] = line[x] + 1
            q.append(nx)

bfs()
print(line[k])

---

오답 풀이

 

처음에는 visited배열을 만들어 한번 접근한 점에는 접근하지 않도록 했는데

생각해보면 한점에 대해 nx들이 시간 소요가 다르기 때문에 먼저 k에 접근한다고 최단시간이 되지 않는다는 것을 알게되었다

그래서 비효율적이지만 모든점에 대해 최소 시간을 구하고 k값을 출력하는 방식으로 하였다