[bfs/백준] 13549번 : 숨바꼭질3

- 문제 : https://www.acmicpc.net/problem/13549

 

Gold Lv5 이고, 스스로 푼 문제다. 

 

문제 이해 

- 기존에 풀었던 숨바꼭질 문제와 비슷한데 다른 점은 x -> 2 * x로 이동할 때 시간이 걸리지 않는다는 점이다.

- 이렇게 이동했을 때 n에서 k로 이동하는데 걸리는 최소 시간을 출력하는 문제다. 

- 이동할 때 시간을 추가하는 거는 분기문으로 나눠서 진행하면되는데

- 문제는 2 * x 로 이동하는데 시간이 걸리지 않으므로 visit했던 노드들도 다시 방문할 경우 시간이 최소가 될 수 있다는 것이다. 

그래서 이부분을 따로 처리해줘야지 틀리지 않는다. 

 

풀이 로직 

- 입력값을 받고, arr를 설정한다. 이때 arr는 10 ** 5 보다 크게해야지 IndexError가 발생하지 않는다. 

- arr값이 0이면 방문하지 않은 지점이고, 0이 아니라면 이전에 방문한 적이 있는 지점이다. 

- x - 1, x + 1, 2 * x 만큼 이동한 nx로 bfs를 진행한다. 

- 이 때 처음 방문하는 노드 (arr[nx] == 0)인 경우에는 방문 처리 후 queue.append(nx) 처리를 해주면 된다.

- 만약 이전에 방문한 노드를 마주쳤다면 (arr[nx] != 0) arr의 값이 최소값인 형태로 변경해주면 된다. 

if nx == 2 * x:
	arr[nx] = min(arr[nx], arr[x])
else:
	arr[nx] = min(arr[nx], arr[x] + 1)

- queue가 빌 때까지 진행한다음에 arr[k] - 1을 출력한다. (arr[k]가 1로 시작하기 때문에 정답이랑 1 차이가 난다)

 

정답 풀이 

from collections import deque

n, k = map(int, input().split())

number = 2 * 10 ** 5
arr = [0] * (number + 1)
arr[n] = 1

queue = deque()
queue.append(n)
while queue:
    x = queue.popleft()
    
    if x == k:
        break
    
    for nx in [x + 1, x - 1, 2 * x]:
        if 0 <= nx <= 10 ** 5:
            if not arr[nx]:
                if nx == 2 * x:
                    arr[nx] = arr[x]
                else:
                    arr[nx] = arr[x] + 1
                queue.append(nx)
            else:
                if nx == 2 * x:
                    arr[nx] = min(arr[nx], arr[x])
                else:
                    arr[nx] = min(arr[nx], arr[x] + 1)
            
print(arr[k] - 1)