[BOJ] 13549. 숨바꼭질 3

문제

숨바꼭질 3 (https://www.acmicpc.net/problem/13549)

풀이

1. 초기 접근

• 문제조건 해석
  • 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다.
    • BFS 문제다.
• 알고리즘
  • 이전 12851. 숨바꼭질 2 문제에서 방법에 약간 변형을 준 것이다.
  • 이전 문제에서는, 현재 위치 cur에서 다음 위치 cur-1, cur+1, cur*2 를 한번에 처리했다면, 이번엔 경우를 나눠야한다.
    • 먼저, visited[cur] 는 cur 위치에 올 때 걸리는 최소 시간을 담는다.
    • cur-1, cur+1 로 이동하는 경우, 현재 위치까지 걸린 시간 + 1 을 해준다.
      즉, visited[cur-1], visited[cur+1] = visited[cur] + 1 이다.
      이 때, 당연히 이 시간 visited[cur] + 1 이 최소시간인지 조건을 붙여야 한다.
    • cur*2 로 이동하는 경우, 현재 위치까지 걸린시간을 그대로 넣어준다.
      즉, visited[cur*2] = visited[cur] 이다.
      마찬가지로 최소시간인지 체크해야 한다.
  • 계속해서 다음 이동좌표를 BFS queue 에 넣어주다가, 최종 목표지점 k에 도달한 경우, 더 이상 넣지않고, 큐에 있는걸 모두 빼낸다.
  • k 에 도달하는데 걸리는 최소시간은 visited[k] 에 있으므로 이를 반환한다.
• 코드

import sys
from collections import deque

n, k = list(map(int, sys.stdin.readline().split()))


def bfs(n, k):
    if n >= k:
        return n-k

    q = deque([n])
    visited = [float('inf')] * 100001
    visited[n] = 0
    success = False

    while q and not success:
        size = len(q)

        for _ in range(size):
            cur = q.popleft()

            # +1, -1의 경우
            next_move = [cur-1, cur+1]
            for j in next_move:
                if j >= 0 and j <= 100000 and visited[cur] + 1 < visited[j]:
                    visited[j] = visited[cur] + 1

                    if j == k:
                        success = True

                    if not success:
                        q.append(j)

            # *2 의 경우2 6
            if cur*2 >= 0 and cur*2 <= 100000 and visited[cur] < visited[cur*2]:
                visited[cur*2] = visited[cur]

                if j == k:
                    success = True

                if not success:
                    q.append(cur*2)

    return visited[k]

print(bfs(n, k))