(Python/🥇4)백준알고리즘 13549번: 숨바꼭질 3

문제 바로가기 

 

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력:

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

풀이:

99 프로에서 틀리는데 이유를 모르겠다..

방금 여러 시도를 해봣는데 .

for next_node in 에 순서를 x-1,x+1,2*X 로 하니깐 맞았다.. 

import sys, heapq
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, k = map(int,input().split())
dp = [-1] * (100001)
dp[n] = 0

Q = deque()
Q.append(n)

while Q:
    x = Q.popleft()
    if x == k:
        print(dp[x])
        break

    for next_node in [x+1, x-1, 2*x]:
        #방문처리
        if 0 <= next_node <= 100000 and dp[next_node] == -1:
            #순간이동일 경우
            if next_node == 2*x :
                dp[next_node] = dp[x]
                Q.appendleft(next_node)
            # 순간이동이 아닐경우
            else:
                dp[next_node] = dp[x] +1
                Q.append(next_node)

 

 

from collections import deque

n, k = map(int, input().split())  
q = deque()
q.append(n) 
visited = [-1 for _ in range(100001)]
visited[n] = 0

while q:
    s = q.popleft()
    if s == k:
        print(visited[s])
        break
    if 0 <= s-1 < 100001 and visited[s-1] == -1:
        visited[s-1] = visited[s] + 1
        q.append(s-1)
    if 0 < s*2 < 100001 and visited[s*2] == -1:
        visited[s*2] = visited[s]
        q.appendleft(s*2)  # 2*s 가 다른 연산보다 더 높은 우선순위를 가지기 위함
    if 0 <= s+1 < 100001 and visited[s+1] == -1:
        visited[s+1] = visited[s] + 1
        q.append(s+1)

 

이렇게 해도 맞다.

그럼 아래꺼 while문 안에 if문 순서를 바꾼다면 ??? 그 역시 틀린다. s-1 부터 시작되어야한다.