[BOJ] 12851. 숨바꼭질 2

문제

숨바꼭질 2 (https://www.acmicpc.net/problem/12851)

풀이

1. 초기 접근

• 문제조건 해석
  • 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다.
    • BFS 문제다.
• 알고리즘
  • 이전 1697. 숨바꼭질 문제에서 경로의 갯수가 추가된 것이다.
  • 이제 우리는 2가지를 생각해야 한다.
    • 하나는, n 까지 오는데의 최소 시간(time) 과 이를 저장하는 방법 (visited[n]) 이고,
    • 다른 하나는, n 까지 최소 시간으로 오는 방법의 수(ways[n])다.
  • 어떤 좌표 j 가 있다고 하자. 이 좌표에 오는 방법에는 3가지 방법이 있을 것이다. (j-1,j+1, j/2 에서 온다.)
    경우가 3가지 이므로, j에 오는 방법은 3가지 일까?
    아니다. 우리는 최소 시간 을 고려해야 한다. 3가지 각 경우에서 j로 갈 때, 어떤게 최소시간인지를 생각해줘야 한다.
  • 예를 들어, j=10 라고 해보자. 9->10, 11->10, 5->10, 이렇게 3가지 경우가 있을텐데, 9->10 으로 갈 때의 시간은 5이고, 11->10은 3, 5->10도 3이라고 해보자.
    이 경우, 11->10과 5->10은 10으로 최소시간만으로 오는 경우이므로, 두 가지 모두 가능하고, 9->10의 경우는 최소시간이 아니므로 (5 > 3 이므로) 이 경우는 불가능하다.
  • 따라서 아래 코드의 조건문에는 범위 체크 뿐 아니라, 해당 방법이 최소시간을 만족하는지 체크하는 time + 1 <= visited[j] 이 들어가게 된다.
• 코드

import sys
from collections import deque

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

def bfs(n, k):
    # n: 시작지점, k: 도착지점

    # 바로바로 처리할 수 있는 경우 2가지.
    if n == k:
        return 0, 1
    if n > k:
        return n-k, 1

    # visited[j] : j 까지 오는데 얼마의 최소 time을 저장.
    # ways[j] : j 까지 최소 time으로 오는 방법의 수 저장.
    q, visited, ways = deque([n]), [float('inf')]*100001, [0]*100001
    time, count, success = 0, 0, False
    ways[n] = 1
    visited[n] = 0

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

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

            next_move = [cur-1, cur+1, cur*2]
            for j in next_move:
                if j >= 0 and j <= 100000 and time + 1 <= visited[j]:
                    ways[j] += 1
                    visited[j] = time + 1

                    if j == k:
                        success = True

                    if not success:
                        q.append(j)
        time += 1

    return visited[k], ways[k]

time, count = bfs(n, k)
print(time)
print(count)