[BOJ] 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는 정수이다.

출력

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

풀이

#bfs

1. 이동 시간을 가장 짧게 하기 위해 순간 이동 탐색을 먼저 진행한다.

 → 이렇게 안했을 때 반례 : 0 2   ⇨ 답) 1 오답) 2 

  답 : 0  → (X+1) → 1 → (순간이동)  → 2

  오답 : 0  → (X+1)  → 1  → (X+1)  → 2

2. 이때 순간 이동 탐색의 경우 큐의 맨 앞에 추가하기 위해 appendleft를 사용한다.

  가중치가 다른 bfs의 경우 큐를 여러 개 만들어 풀 수 있다. deque를 활용하면 앞(appendleft)뒤(append)로 넣을 수 있기 때문에 하나의 deque로 구현할 수 있다.

코드

from collections import deque

N, K = map(int, input().split())

q = deque()
q.append(N)

visited = [-1 for _ in range(100001)]
visited[N]=0

def bfs():
    while q:
        cur = q.popleft()
        if cur == K:
            return visited[cur]

        # 0초 뒤 순간 이동
        if 0 < cur * 2 < 100001 and visited[cur * 2] == -1:
            q.appendleft(cur * 2)
            visited[cur * 2] = visited[cur]

        # 1초 뒤 X-1
        if 0 <= cur-1 < 100001 and visited[cur-1]==-1:
            q.append(cur-1)
            visited[cur-1] = visited[cur] + 1

        # 1초 뒤 X+1
        if 0 <= cur+1 < 100001 and visited[cur+1]==-1:
            q.append(cur+1)
            visited[cur+1] = visited[cur] + 1



print(bfs())