코딩테스트

백준 12851. 숨바꼭질 2

말하는 감자에요 2025. 4. 19. 20:36
728x90
반응형

오늘은 숨바꼭질 시리즈의 2탄, 백준 12851번 숨바꼭질 2를 풀어보았습니다.

1편에서는 단순히 동생을 찾는 데 걸리는 최소 시간만 구했다면,

이번 문제에서는 거기서 한 발 더 나아가서:

“최단 시간으로 도착하는 방법의 수”까지 함께 구해야 합니다.

그럼 바로 문제를 살펴볼까요?

1. 문제: 백준 12851. 숨바꼭질 2

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

예제 입력 1

5 17

예제 출력 1

4
2

2. 문제 풀이

✅ BFS로 최단 시간 탐색

최단 시간(최단 거리)을 구하는 문제는 변함없이 BFS를 사용합니다.

숨바꼭질 1과 동일하게, 0 ~ 100000 범위의 노드를 탐색하면서

매번 가능한 3가지 이동을 큐에 넣어가며 탐색하면 됩니다.

✅ 그런데, 이번엔 경로의 수까지 구해야 한다?

수빈이가 동생에게 도달하는 모든 경로 중 최소 시간 경로가 여러 개일 수 있습니다.

따라서, 아래 정보를 함께 저장하며 BFS를 진행해야 합니다:

  • visited[x]: x까지 도달하는 데 걸린 최소 시간
  • ways[x]: x까지 도달하는 최소 시간 경로의 수

✅ 구현 아이디어 요약

  1. visited[]: x 지점을 처음 방문한 시간 저장
  2. ways[]: x에 도달하는 최소 시간의 경로 개수 저장
  3. BFS 탐색 중,
    • 처음 도달한 경우: visited[x] 초기화, ways= ways[cur]
    • 이미 방문했지만 같은 시간에 또 도달한 경우: ways+= ways[cur]

구현 코드

from collections import deque
def bfs(N, K):
    queue = deque([N])
    visited = [-1] * 100001
    ways = [0] * 100001

    visited[N] = 0
    ways[N] = 1

    while queue:
        cur_x = queue.popleft()

        for next_x in (cur_x - 1, cur_x + 1, 2 * cur_x):
            if 0 <= next_x <= 100000:
                if visited[next_x] == -1:
                    visited[next_x] = visited[cur_x] + 1
                    ways[next_x] = ways[cur_x]
                    queue.append((next_x))
                elif visited[next_x] == visited[cur_x] + 1:
                    ways[next_x] += ways[cur_x]

    return visited[K], ways[K]

def main():
    N, K = map(int, input().split())
    print(*bfs(N, K), sep='\\n')

if __name__ == '__main__':
    main()

3. 마무리

숨바꼭질 1편에서는 단순한 BFS로 최단 시간만 구했지만, 이번 문제에서는 최단 시간 경로의 수까지 고려해야 해서 조금 더 세심한 상태 관리가 필요했습니다.

BFS로 탐색하면서 "같은 시간에 도달하는 경우"를 더 누적해서 기록해야 한다는 점이 포인트였습니다.

 

다음은 숨바꼭질 시리즈의 3탄, 숨바꼭질 3 (백준 13549)입니다.

 

이 문제에서는 이동 방법마다 시간이 다르게 걸리는 경우(0초/1초)를 다루게 되므로, 0-1 BFS라는 새로운 개념이 필요합니다.

그럼 다음 글에서 이어서 만나보겠습니다!

728x90
반응형