⭐ 숨바꼭질 3

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	63310	18196	11731	25.215%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

2

---

⭐ 풀이 과정

bfs로 풀어야 한다는 생각은 쉽게 했지만 그 외에 놓친 부분이 많았다.

1. visited 여부를 체크하지 않아서 시간초과

visited 배열을 만들어야 하는 이유 : 만약 위치 5를 이미 방문했다고 가정하자. 그리고 다시 5를 방문하게 되면 이미 갔었던 루트를 또 가게 되는 것이다. 이건 이미 최소시간 루트가 될 수 없다. visited 여부를 체크하지 않아도 테스트 케이스는 통과하지만 시간초과가 될 가능성이 크니 visited 여부를 체크해주자!

2. 순간이동하는 경우를 최우선으로 생각하지 않아서 틀림

순간이동을 하는 경우 걸리는 시간은 0초이다.
이를 고려해서 순간이동->x+1로 이동->x-1로 이동 순서로 큐에 넣어주었지만 이것도 오답으로 처리됐다...

if (2*x) <= 100000 and visited[2*x] == False: # 1. 순간이동 
    visited[2*x] = True
    queue.append([2*x, count])
if (x+1) <= 100000 and visited[x+1] == False: # 2. x+1로 이동 
    visited[x+1] = True
    queue.append([x+1, count+1])
if (x-1) >= 0 and visited[x-1] == False: # 3. x+1로 이동
    visited[x-1] = True
    queue.append([x-1, count+1])

왜냐면 순간이동하는 경우를 최우선으로 생각하지 않아서이다.
순간이동만 해서 도착지점에 도착할 수 있다면, 그것이 가장 짧은 시간에 도달할 수 있는 경로인 것이다.
순간이동만의 경우를 최우선으로 생각해야 하기 때문에 queue.appendleft([2*x, count]) 해주어야 한다. 만약 이렇게 하지 않으면 시간을 써서 간 경로가 먼저 계산되기 때문에 while문을 탈출하게 되어 오답이 출력된다.

---

⭐ 코드

from collections import deque


n, k = map(int, input().split())
queue = deque()
visited = [False] * 100001

def bfs(start):
    visited[start] = True
    queue.append([start, 0])
    
    while queue:
        x, count = queue.popleft()
        if x == k:
            print(count)
            break
        if (2*x) <= 100000 and visited[2*x] == False:
            visited[2*x] = True
            queue.appendleft([2*x, count]) # 순간이동 하는 경우는 최우선으로 생각하여 큐 맨 앞에 넣는다.
        if (x+1) <= 100000 and visited[x+1] == False:
            visited[x+1] = True
            queue.append([x+1, count+1])
        if (x-1) >= 0 and visited[x-1] == False:
            visited[x-1] = True
            queue.append([x-1, count+1])
        
bfs(n)