[BOJ] 12851 - 숨바꼭질 2

💻 백준 12851번: 숨바꼭질 2

문제 링크: https://www.acmicpc.net/problem/12851
알고리즘 분류: 너비 우선 탐색(BFS), 그래프 이론

문제 소개 🧐

수빈이가 동생을 찾는 ‘숨바꼭질’ 문제의 확장판이다. 수빈이는 점 N에 있고 동생은 점 K에 있다. 수빈이는 걷기(X-1, X+1) 또는 순간이동(2*X)을 할 수 있으며, 각각 1초가 걸린다.

이 문제에서는 동생을 찾는 가장 빠른 시간뿐만 아니라, 그 시간으로 찾는 방법의 수까지 구해야 한다.

입력 📝

첫 번째 줄에 수빈이의 위치 N과 동생의 위치 K가 주어진다. (0 ≤ N, K ≤ 100,000)

출력 📤

첫째 줄에 가장 빠른 시간을, 둘째 줄에는 그 방법의 수를 출력한다.

첫 번째 시도: DP로 접근하기 🤯

Idea

처음에는 동적 프로그래밍(DP)으로 접근했다. 각 위치 i에 도달하는 데 걸리는 최소 시간을 저장하고, 어떻게 도달했는지에 따라 경우를 나누려고 했다.

dp[i][0]: i/2 위치에서 순간이동으로 온 경우
dp[i][1]: i-1 위치에서 걸어서 온 경우
dp[i][2]: i+1 위치에서 걸어서 온 경우

이렇게 3차원 배열을 만들어 각 위치에 도달하는 최소 시간을 갱신해나가는 방식으로 풀고자 했다.

Code

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

sys.setrecursionlimit(300000)

if N > K:  # 동생이 누나보다 뒤
    print(N-K, 1, sep='\n')
    exit()

dp = [[float('inf') for _ in range(3)] for _ in range(100001)]

dp[N][0], dp[N][1], dp[N][2] = 0, 0, 0
dp[0][2] = N
visited = [False] * 100001

q = deque()
q.append(N)

while q:

    i = q.popleft()

    if visited[i]:
        continue
    else:
        visited[i] = True

    if i < 50000:
        dp[2*i][0] = min(min(dp[i]) + 1, dp[2*i][0])
        q.append(2*i)
    
    if i < 100000:
        dp[i+1][1] = min(min(dp[i]) + 1, dp[i+1][1])
        q.append(i+1)
    
    if i > 0:
        dp[i-1][2] = min(min(dp[i])+ 1, dp[i-2][2])
        q.append(i-1)

cnt = 0
min_time = min(dp[K])

for i in range(3):
    if dp[K][i] == min_time:
        cnt += 1

print(min_time, cnt, sep='\n')

Result

결과: 46% 시간 초과 및 실패 😭
visited 배열을 사용한 것이 가장 큰 문제였다. 어떤 지점에 한 번 방문하면 다른 경로로 같은 시간에 도달하는 경우를 무시하게 된다.
예를 들어, 4에 도달하는 방법이 2 -> 4 (순간이동)과 3 -> 4 (걷기) 두 가지가 같은 시간에 가능하더라도, visited 때문에 하나만 처리된다. DP 상태 정의도 복잡하고 경로의 수를 세기에는 부적합했다.

두 번째 시도: BFS와 경로 수 기록 ✨

Idea

최단 거리는 BFS의 특성을 활용하면 자연스럽게 구할 수 있다. 여기에 각 지점까지의 최단 경로가 몇 개인지 세는 배열을 추가하면 문제를 해결할 수 있다.

dist 배열: 시작점(N)에서 각 지점까지의 최단 시간을 저장한다. -1로 초기화하여 방문 여부를 겸한다.
cnt 배열: 시작점에서 각 지점까지 최단 시간으로 도달하는 방법의 수를 저장한다.
BFS를 순회하면서 다음 지점 nx를 탐색한다.
- nx에 처음 방문하는 경우 (dist[nx] == -1): 최단 시간을 기록하고(dist[nx] = dist[x] + 1), 방법의 수는 이전 지점의 방법의 수를 그대로 가져온다(cnt[nx] = cnt[x]).
- nx에 이미 방문했지만, 같은 최단 시간으로 또 도달한 경우 (dist[nx] == dist[x] + 1): 최단 시간은 그대로 두고, 방법의 수만 더해준다(cnt[nx] += cnt[x]).

Code

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

q = deque()
q.append(N)

dist = [-1] * 100001
cnt = [0] * 100001

dist[N] = 0
cnt[N] = 1

while q:
    x = q.popleft()

    for nx in (x*2, x+1, x-1):
        if 0 <= nx < 100001:
            if dist[nx] == -1:  # nx에 첫 방문
                dist[nx] = dist[x] + 1
                cnt[nx] = cnt[x]
                q.append(nx)
            
            # 같은 최단시간으로 방문
            elif dist[nx] == dist[x] + 1:
                cnt[nx] += cnt[x]

print(dist[K])
print(cnt[K])

Result

결과: 성공! 🎉
BFS를 사용해 최단 시간을 찾는 동시에, cnt 배열로 경로의 수를 누적하는 방식이 정확하게 들어맞았다. visited 배열 없이 dist 배열만으로 방문 여부와 최단 시간을 관리하는 것이 핵심이었다.

배운 점 및 개선할 부분 🤔

BFS의 응용: 단순 최단 거리뿐만 아니라, 최단 경로의 ‘개수’를 세는 문제에도 BFS를 효과적으로 적용할 수 있다는 것을 배웠다.
상태 값의 중요성: visited와 같은 boolean 배열로 상태를 단순하게 관리하면 다양한 경우의 수를 놓칠 수 있다. 이 문제처럼 ‘최단 시간’과 ‘경로의 수’라는 두 가지 정보가 필요할 때는, 각각을 저장할 별도의 배열을 두고 상태를 더 구체적으로 정의해야 한다.
재방문의 의미: BFS에서 어떤 노드를 다시 방문하게 되는 경우는 보통 최단 경로가 아니므로 무시한다. 하지만 이 문제에서는 ‘같은 최단 시간’으로 재방문하는 경우가 핵심 단서가 되었다. 문제의 조건에 따라 재방문의 의미를 다르게 해석해야 한다는 점을 깨달았다.

최단 경로 문제에서 경우의 수를 세어야 한다면, BFS를 진행하며 각 노드에 도달하는 경로의 수를 함께 기록하는 방법을 떠올리자.

⁂