숨바꼭질3[백준13549] - python

숨바꼭질 시리즈 3번째 문제다

 

정답 코드 먼저 살펴보자

from collections import deque
n, k = map(int, input().split())

location = [-1] * 100001
time = 0
queue = deque()
queue.append([n, time])
location[n] = 0

while queue :
  curr_n, curr_time = queue.popleft()

  next_n = curr_n * 2
  if 0 <= next_n <= 100000 and (location[next_n] == -1 or location[next_n] > curr_time):
    location[next_n] = curr_time
    queue.appendleft([next_n, curr_time])

  next_n = curr_n + 1
  if next_n <= 100000 and location[next_n] == -1 :
    location[next_n] = curr_time + 1
    queue.append([next_n, curr_time + 1])
  
  next_n = curr_n - 1
  if next_n >= 0 and location[next_n] == -1:
    location[next_n] = curr_time + 1
    queue.append([next_n, curr_time + 1])

print(location[k])

 

0초에 순간이동 해주는게 핵심이다. 

bfs로 접근을 하였고 순간이동을 하는 경우는 bfs의 가장 첫번째로 appendleft를 시켜주었다. 

 

순간이동을 할때 조건문을 잘 봐야 하는데

1. 방문한 적이 없거나

2. 방문예정인 곳의 시간 정보가 현재보다 클때이다 예를들면
i) 4 -> 3 -> 6 -> 12

ii) 4 -> 5 -> 6 -> 12 

 

6에 접근을 하는 경우가 i)의 경우 1, ii)의 경우 2이다. 

내 코드에서는 ii)의 경우가 먼저 6에 접근이 되었고 i)의 경우에서 6에 접근할때 기존 6에 업데이트를 해주어야 했다.

>= 조건을 사용할 경우 같은 값일때도 들어가서 불필요한 경우에도 queue에 append가 되어서 while이 종료되지 않은 경우도 있을수 있다. 시간 정보를 업데이트 해줄때만 필요하므로 주의해주자!!

 

 

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3