백준 13549 python [숨바꼭질 3]

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

from collections import deque


# with open('./data.txt', 'r') as file:
#     data = file.read().split(" ")

data = input().split(" ")

N, K = map(int, data)
MAX = 200000
graph = [-1] * (MAX + 1)


def bfs(now, taret):
    Q = deque()
    Q.append(now)
    graph[now] = 0
    
    while Q:
        current = Q.popleft()
        
        if(current == taret):
            return graph[current]
        
        a = current * 2
        b = current + 1
        c = current - 1
        
        # 순간이동 먼저
        if(a <= MAX and graph[a] == -1):
            graph[a] = graph[current]
            Q.appendleft(a)
          
        if(c >= 0 and graph[c] == -1):
            graph[c] = graph[current] + 1
            Q.append(c)
            
        if(b <= MAX and graph[b] == -1):
            graph[b] = graph[current] + 1
            Q.append(b)
        
            
print(bfs(N, K))

생각

이번 문제의 알고리즘 분류를 보면 0-1 너비 우선 탐색이 있다.

혹시나해서 찾아보니 간선의 가중치가 0,1 두개뿐인 그래프에서
최단 경로를 찾기 좋은 알고리즘이다. 라고 하여
해당 알고리즘을 공부하고 적용하여 풀었다.

0-1 너비 우선 탐색 알고리즘의 특성으로는 가중치가 0인 경로를
deque 맨 앞에 넣고 제일 먼저 탐색하게 하는 것이다.

즉 가중치가 적은것부터 탐색하여 최단경로를 구하는 것

큐와 deque의 차이점은 큐는 FIFO 원칙을 따르지만
deque는 맨 앞에도 삽입이 가능하다고 한다.

그래서 *2를 한 값들이 제일 먼저 방문될것이다. 아래처럼.
*2 먼저 다 방문하고 -1, +1 노드 방문

## 5
## 10
## 20
## 40
## 80
## 160
## 320
## 640
## 1280
## 2560
## 5120
## 10240
## 20480
## 40960
## 81920
## 163840

풀이

0-1 너비 우선 탐색의 가장 기본적인 구현을 요구하는 것 같다.

deque의 값이 목적지와 동일할 때 까지 아래의 로직을 반복해주면 된다.

*2 노드들만 다 먼저 방문해서 방문처리를 해주고
나머지 -1, +1 노드들을 방문해주며 현재 노드 값 +1을 해주기

주의할점은 -1 노드보다 +1 노드를 먼저 deque에 넣으면 실패하게 된다.

해당 문제에만 국한된건진 모르겠지만 +1을 먼저 넣게 되면
최단 경로가 달라지게 되는 것 같다.