백준: 13549 숨바꼭질 3

숨바꼭질 시리즈

• 숨바꼭질
• 숨바꼭질 2
• 숨바꼭질 3
• 숨바꼭질 4

 

문제

13549번: 숨바꼭질 3

 

문제 풀이

 기본적인 풀이 방식은 1697 숨바꼭질과 같다. 하지만 순간이동 할 경우, 0초의 시간이 걸리므로 순간이동 하는 경우에 우선순위를 두어 처리하여야 한다. 즉, 가중치를 가지는 그래프가 된다는 것과 같다. 만약 현재 위치 - 1, 현재 위치 + 1, 현재 위치 * 2의 우선 순위가 각각 다르다면 다익스트라로 풀어야 한다. 하지만 문제에서는 현재 위치 * 2(순간 이동)인 경우만 우선적으로 처리하면 되기에 BFS로 풀 수 있다.

 

코드

from sys import stdin
from collections import deque


def bfs(start):
    q = deque([start])

    while q:
        cur_loc = q.popleft()
        if cur_loc == k:
            return visited[cur_loc]

        for next_loc in (cur_loc - 1, cur_loc + 1, cur_loc * 2):
            if 0 <= next_loc < MAX_LOC and not visited[next_loc]:
                visited[next_loc] = visited[cur_loc]

                if next_loc == cur_loc * 2 and cur_loc > 0:
                    q.appendleft(next_loc)
                else:
                    visited[next_loc] = visited[cur_loc] + 1
                    q.append(next_loc)


if __name__ == '__main__':
    MAX_LOC = 100001
    n, k = map(int, stdin.readline().split())
    visited = [0] * MAX_LOC
    print(bfs(n))

 순간이동 (현재위치 * 2)에 우선순위를 두기 위해, 곱하기 인 경우 큐의 좌측에 삽입하여 먼저 처리 될 수 있도록 하였다.