백준 13549 숨바꼭질3

haruponea·2021년 3월 24일
0

BOJ

목록 보기
24/41

문제 링크 https://www.acmicpc.net/problem/13549

풀이
BFS같아 보이지만 단순한 BFS로는 풀 수 없는 문제였습니다. 0-1BFS를 사용해서 풀었는데 가중치가 0인 경로는 큐의 앞에 1인 경로는 큐의 뒤에 삽입을 하면 됩니다. 하지만 큐는 앞에 삽입하는 자료구조가 아니기 때문에 덱을 사용하면 풀 수 있고 또는 우선순위 큐를 사용할 수 있습니다.

Python

from collections import deque
>
start, goal = map(int, input().split())
board = [-1]*100001
q = deque()
q.append(start)
board[start] = 0
while q:
    cur = q.popleft()
    if cur == goal:
        print(board[goal])
        break
    if 0 <= cur*2 <= 100000 and board[cur*2] == -1:
        q.appendleft(cur * 2)
        board[cur*2] = board[cur]
    for next in [cur - 1, cur + 1]:
        if 0 <= next <= 100000 and board[next] == -1:
            board[next] = board[cur] + 1
            q.append(next)

0개의 댓글