[Python/파이썬] 백준 알고리즘 13549 - 숨바꼭질 3 (BFS)

 

 

 

<풀이>

기존 숨바꼭질 문제에서는 모든 가중치가 1이었다.

이 문제의 차이점은 순간이동하는 경우는 0으로 가중치가 다르다는 것이다.

 

순간이동은 0초가 걸리고 걷기는 1초가 걸리므로 큐를 2개로 나눠 구현하면 된다.

 

이때 양방향 큐인 deque를 활용하면 별도의 큐를 더 생성하지 않고 구현할 수 있다.

 

순간이동하는 경우는 appendleft로 맨앞에 추가해주고 걷는 경우는 append로 뒤에 추가해주면 된다.

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
road = [0] * 100001

queue = deque()
queue.append(N)
road[N] = 1
while queue:
    popN = queue.popleft()
    if popN == K:
        print(road[K]-1)
        break
    for newN in (2*popN, popN-1, popN+1):
        if 0 <= newN < 100001 and road[newN] == 0:
            if newN == 2*popN:      # 순간 이동 하는 경우
                road[newN] = road[popN]
                queue.appendleft(newN)
            else:                   # 걸어서 이동 하는 경우
                road[newN] = road[popN] + 1
                queue.append(newN)

road배열의 초기화를 0으로 해주었고 시작점의 초기 값을 1로 했으므로 print할 때 값에서 1을 빼준다.

 

 

 

<핵심 정리>

1. 가중치가 다른 bfs문제의 경우 큐를 여러개 만들어 푼다. 이때 deque를 활용하면 appendleft로 구현할수도 있다.

2. bfs,dfs문제에서 범위는 항상 문제에서 주어진 조건 범위를 다 잡아놓자 (ex. 0 <= newN < 100001 / N <= newN < 100001로 했다가 틀렸다 ㅠ 잘못생각했다..)