[백준] 13549 파이썬(python) : 숨바꼭질 3 - 0-1 BFS

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

13549번: 숨바꼭질 3

 

 

from collections import deque
n, k = map(int, input().split())
visit = [0] * 100001

def bfs(v):
    q = deque()
    q.append(v)
    while q:
        x = q.popleft()
        if x == k: #1
            return visit[x]
        for nx in (x-1, x+1, 2*x): #2
            if 0 <= nx < 100001:
                if not visit[nx]:
                    if nx == 2*x and nx != 0: #3
                        visit[nx] = visit[x] #4
                        q.appendleft(nx) #5
                    else: #6
                        visit[nx] = visit[x] + 1 #7
                        q.append(nx) #8
print(bfs(n))

 

#1 : 탈출조건 원하는 위치에 도달하면 그때의 시간 출력

#2 : 각각 한칸 뒤로, 한칸 앞으로 그리고 2배거리 순간이동

#3 : 순간이동하는 경우라면 가중치가 0이므로 

#4 : 시간추가 없이 다음거리에 그대로 복사

#5 : 가중치가 0이므로 0-1 BFS 알고리즘에 의해 큐의 앞(front)에 삽입

#6 : 순간이동이 아닌 걷는 2가지 경우라면

#7 : 1초가 걸리니까 시간 1씩 추가

#8 : 그리고 가중치가 1이어서 낮으니까 뒤에 삽입

 

0-1 BFS 알고리즘을 사용해야 하는 문제다. 가중치가 다른 경우 큐를 2개로 나눠서 접근해야 한다. 하지만 그것을 몰랐기 때문에 #5가 도저희 이해가 되지 않았고 해당 알고리즘을 공부하고 난 뒤에서야 가중치 0인 노드를 방문하고 나서는 큐의 앞에 넣어줘야 원하는 정렬이 이루어진다는것을 알았다.

 

https://hgk5722.tistory.com/167?category=1032384 

[Algorithm] 0-1 BFS