백준 1285번: 숨바꼭질 2

2024.10.30 - [알고리즘/백준] - 백준 1697번- 숨바꼭질

백준 1697번- 숨바꼭질

이전 문제에서 최소 거리로 가는 방법을 구하는 경우의 수까지 구해줘야 하는 문제이다.

저번에는 도착 지점에 최소 거리로 도달하면 그 거리만 출력하면 되는거였지만 이번에는 그 최소 거리가 몇 번 가능한지 경우의 수까지 구해줘야 하는 것이다.

 

 

from collections import deque

def bfs(n, k):
    # 방문 시간을 기록하는 배열 (-1은 방문하지 않았음을 의미)
    visited = [-1 for _ in range(100001)]  # 0~100000 범위
    queue = deque([(n, 0)])  # (현재 위치, 현재 시간)
    visited[n] = 0  # 시작 위치의 방문 시간은 0
    min_time = float('inf')  # 최소 시간을 저장
    ways = 0  # 최소 시간으로 도달 가능한 경로 수

    while queue:
        current_node, current_second = queue.popleft()

        # 목표 노드에 도달한 경우 처리
        if current_node == k:
            if current_second < min_time:  # 더 짧은 시간에 도달한 경우
                min_time = current_second
                ways = 1  # 새로운 최소 시간 경로
            elif current_second == min_time:  # 같은 시간에 도달한 경우
                ways += 1
            continue

        # 다음 이동 가능한 위치 탐색
        for next_node in [current_node - 1, current_node + 1, current_node * 2]:
            if 0 <= next_node <= 100000:  # 범위 확인
                # 처음 방문하거나, 동일 시간에 다시 방문 가능한 경우
                if visited[next_node] == -1 or visited[next_node] == current_second + 1:
                    visited[next_node] = current_second + 1  # 방문 시간 갱신
                    queue.append((next_node, current_second + 1))  # 큐에 추가

    # 결과 출력
    print(min_time)  # 최소 시간
    print(ways)      # 최소 시간으로 목표에 도달한 경로 수

# 입력
n, k = map(int, input().split())
bfs(n, k)

처음에 틀렸던 이유

처음에는 한 번 방문한 노드는 다시 방문하지 않도록 설정했습니다. 이는 BFS의 최단 거리 탐색 원칙에 부합하지만, 최단 거리로 도달할 수 있는 모든 경로를 탐색하지 못하는 문제가 있었습니다.

문제점

 

• 같은 노드에 도달할 수 있는 경로가 여러 개일 수 있으며, 그중 다른 경로를 통해 동일한 시간에 도달할 수 있습니다.
• 한 번 방문한 노드를 다시 탐색하지 않으면, 최단 시간에 도달할 수 있는 모든 경우의 수를 계산하지 못하게 됩니다.

해결 방안

최초 방문 및 동일 시간 허용 조건 추가

• 노드가 처음 방문된 경우(visited[next_node] == 0)에는 탐색을 진행.
• 동일한 시간(visited[next_node] == current_second + 1)에 도달 가능한 경우를 허용하여 경로 수를 누적.

입력: N = 5, K = 17

---

 

 

시간 (초)	현재 큐 상태	현재 노드	방문 배열 (visited)	설명
0	deque([(5, 0)])	5	visited[5] = 0	시작 위치 5를 방문, 방문 시간 0으로 설정.
1	deque([(4, 1), (6, 1), (10, 1)])	5	visited[4] = 1, visited[6] = 1, visited[10] = 1	위치 4, 6, 10 방문, 시간 1로 설정.
2	deque([(6, 1), (10, 1), (3, 2), (8, 2)])	4	visited[3] = 2, visited[8] = 2	위치 3, 8 방문, 시간 2로 설정.
2	deque([(10, 1), (3, 2), (8, 2), (7, 2), (12, 2)])	6	visited[7] = 2, visited[12] = 2	위치 7, 12 방문, 시간 2로 설정.
2	deque([(3, 2), (8, 2), (7, 2), (12, 2), (9, 2)])	10	visited[9] = 2	위치 9 방문, 시간 2로 설정.
3	deque([(8, 2), (7, 2), (12, 2), (9, 2), (2, 3)])	3	visited[2] = 3	위치 2 방문, 시간 3로 설정.
...	...	...	...	계속 탐색하며 목표 위치 17에 도달.
4	deque([(17, 4)])	17	visited[17] = 4	위치 17에 도달. 최소 시간 4 확인, 경로 수 누적.