[백준/파이썬] #13549

테스트 케이스는 맞았는데 틀렸다고 떴다. 30분 이상 풀어도 잘 모르겠어서 풀이를 참고했다. 

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
visited = [False] * (100000+1)
answer = 100000
visited[N] = True
queue = deque([(0, N)])

if N == K:
    print(0)

else:
    while queue:
        current_time, current_position = queue.popleft()
        
        if current_position == K:
            answer = min(answer, current_time)
        
        if 0 <= current_position+1 <= 100000 and not visited[current_position+1]:
            visited[current_position+1] = True
            queue.append((current_time+1, current_position+1))
        if 0 <= current_position-1 <= 100000 and not visited[current_position-1]:
            visited[current_position-1] = True
            queue.append((current_time+1, current_position-1))
        if 0 <= current_position * 2 <= 100000 and not visited[current_position*2]:
            visited[current_position*2] = True
            queue.append((current_time, current_position * 2))
       
    print(answer)

 

deque를 순회하는 점은 비슷했는데, visited로 방문 여부를 저장하는 게 아니라 time[]으로 해당 위치를 방문했을 때의 시간의 최솟값을 저장했어야 했다.

 

그리고 N=0, K=1인 경우는 엣지 케이스라고 한다..! 

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
time = [0] * (100000+1)


def bfs(start, end):
    queue = deque()
    if start == 0:
        queue.append(1)
    else:
        queue.append(start)

    while queue:
        current = queue.popleft()
        if current == end:
            return time[current]
        
        for next in (current-1, current+1, current*2):
            if 0 <= next <= 100000 and time[next] == 0:
                if next == 2 * current:
                    time[next] = time[current]
                    queue.appendleft(next)
                else:
                    time[next] = time[current] + 1
                    queue.append(next)


if N == 0 and K == 0:
    print(0)
elif N == 0:
    print(bfs(N, K) + 1)
else:
    print(bfs(N, K))