(Python) - BOJ(13549번) : 숨바꼭질 3

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

13549번: 숨바꼭질 3

---

• 문제 : 

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

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

 

 

 

---

• 풀이 :

x-1, x-1, x*2의 경우를 bfs로 탐색한다. 이 때, *2 연산의 경우 가중치가 0이므로 먼저 모든 경우를 계산해 주어야 한다.

예를 들어, 1에서 8로 가는상황이라고 하면 가중치가 0인 *2를 우선처리할 경우 1 -> 2 -> 4 -> 8에서 총 0의 시간이 걸려야 한다. 

 

따라서 우선순위 큐를 쓰거나, 또 다른 방법으로는 python이 지원하는 deque를 사용하여 *2연산에 대해서는 가중치를 증가시키지 않고 appendleft로 큐 앞에 넣어주었다.

 

처음에 계속 틀렸습니다가 나왔는데 반례를 찾느라 몇 시간동안 고생했다.

 

가중치가 없는 *2 연산에 우선순위를 주려면 deque에서 popleft한 값을 확인할 때도 *2 연산부터 확인했어야 했다.

반례는

1 2

답 : 0

출력 : 1

이었다. 그 이유는 curr+1이 먼저 계산되어 2로 갈 때 가중치가 1 필요하다고 계산되었기 때문이다. 

 

또한 다른 아이디어로 *2 연산이라면 M이 무조건 짝수여야만 갈 수 있다고 생각하여 M이 짝수일때만 deque를 사용하고 아닐 때는 일반 BFS처럼 푸는 아이디어를 생각했다.

 

구현하다 보니 당연히 에러가 생겼는데 그 이유는 M이 홀수더라도 가중치가 0인 연산을 하지 않으면 가중치가 1인 연산이 우선처리되어 *2 연산으로 갈 수 있는(가중치 누적이 더 적은) 경우를 처리하기 때문이다.

 

---

• 소스코드 : 

from collections import deque
N,M = map(int,input().split())

visited = [-1]*100001
queue = deque()
queue.append(N)
visited[N] = 0
while queue:
    curr = queue.popleft()
    if curr == M:
        print(visited[M])
        break
    if 0 <= curr*2 <= 100000:
        if visited[curr*2] == -1:
            visited[curr*2] = visited[curr]
            queue.appendleft(curr * 2)
    for i in [curr+1, curr-1]:
        if 0 <= i <= 100000:
            if visited[i] == -1:
                visited[i] = visited[curr] + 1
                queue.append(i)