백준 1697번- 숨바꼭질

문제 요약

수빈이는 현재 위치 N에 있고, 동생은 위치 K에 있다. 수빈이가 이동할 수 있는 세 가지 방법은 다음과 같다:

1. 한 칸 뒤로 가기: 현재 위치에서 -1만큼 이동 (X - 1)
2. 한 칸 앞으로 가기: 현재 위치에서 +1만큼 이동 (X + 1)
3. 순간이동하기: 현재 위치에서 *2만큼 이동 (2 * X)

각 이동은 1초가 걸리며, 수빈이가 동생의 위치 K에 도달하는 데 걸리는 최소 시간을 구하는 것이 목표이다.

알고리즘 설명

최단 시간을 구하는 문제는 BFS(너비 우선 탐색)로 해결하는 것이 적합하다. 이유는 다음과 같다:

• BFS는 최단 경로를 보장한다. 한 단계씩 모든 가능한 위치를 탐색하기 때문에, 목표 위치에 가장 먼저 도달한 경로가 곧 최단 경로가 된다.
• DFS(깊이 우선 탐색)는 한 경로를 끝까지 탐색하므로 최단 경로를 찾지 못할 가능성이 크고, 시간이 오래 걸릴 수 있다.

따라서 이 문제에서는 BFS를 사용해 각 위치를 탐색하면서, 동생의 위치에 가장 먼저 도달했을 때의 시간을 구하는 것이 최적의 방법이다.

코드

import sys
from collections import deque

input = sys.stdin.readline

def bfs(n, k):
    # 각 위치의 최소 이동 시간을 저장할 리스트 초기화
    # 방문하지 않은 위치는 -1로 설정하여 방문 여부 확인 가능
    visited = [-1 for i in range(100001)]
    visited[n] = 0  # 시작 위치의 이동 시간을 0으로 설정
    queue = deque([n])  # 시작 위치를 큐에 추가하여 탐색 시작

    # BFS 탐색 시작
    while queue:
        current_node = queue.popleft()  # 현재 위치를 큐에서 꺼냄

        # 목표 위치에 도달하면 해당 위치의 이동 시간을 반환
        if current_node == k:
            return visited[current_node]

        # 현재 위치에서 이동 가능한 다음 위치들을 확인
        for next_node in [current_node - 1, current_node + 1, 2 * current_node]:
            # 다음 위치가 범위 내에 있고, 아직 방문하지 않았다면
            if 0 <= next_node <= 100000 and visited[next_node] == -1:
                # 다음 위치의 이동 시간은 현재 위치의 시간 +1
                visited[next_node] = visited[current_node] + 1
                queue.append(next_node)  # 다음 위치를 큐에 추가하여 탐색을 이어감

# 입력 처리: 수빈의 시작 위치(n)와 동생의 위치(k)를 입력받음
n, k = map(int, input().split())

# BFS 탐색을 통해 최단 시간 출력
print(bfs(n, k))

 

 

그래프 탐색을 처음 시도할 때, 각 노드가 무엇을 의미하는지 이해하는 것이 중요하다. 그래프 탐색에서는 각 노드에서 어디로 이동할 수 있는지를 파악해야 BFS나 DFS를 효과적으로 사용할 수 있기 때문이다.

이 문제에서 노드의 개념은 위치이다. 예를 들어, 수빈이가 위치 5에서 출발할 때, 그는 이동할 수 있는 세 가지 방법이 있다: -1, +1, *2를 통해 4, 6, 10의 위치로 이동하는 것이다. 이처럼 특정 위치에서 갈 수 있는 다음 위치들을 파악하고, 이를 하나씩 탐색하며 이동을 반복하는 것이 그래프 탐색을 통해 문제를 푸는 방식이다.

이제 BFS를 적용하는 과정을 살펴보자. BFS에서는 시작점에서 목표 지점까지의 최단 경로를 탐색할 수 있는데, 각 위치를 방문하면서 이동할 때마다 이전 위치에서 +1만큼 이동한 횟수를 기록하게 된다.

1. 예를 들어, 수빈이가 위치 5에서 출발한다면, 처음 위치이므로 visited[5] = 0이다 (0번 움직였음을 뜻함).
2. 5에서 갈 수 있는 위치는 4, 6, 10이다. 이 위치들은 모두 5에서 +1만큼 이동한 위치이므로, visited[4], visited[6], visited[10]은 각각 visited[5] + 1로 설정된다. 즉, visited[4] = 1, visited[6] = 1, visited[10] = 1이 된다.
3. 이제 큐에서 4, 6, 10을 꺼내서 각 위치에서 갈 수 있는 새로운 위치들을 다시 탐색하고, 마찬가지로 이동 횟수를 +1씩 더하면서 진행한다. 이렇게 하면 모든 위치에 대해 최소 이동 횟수를 기록할 수 있게 된다.

BFS와 DFS의 차이점

만약 DFS를 사용하게 되면, 수빈이가 시작 위치에서 가능한 경로를 끝까지 탐색한 후에야 다른 경로를 탐색하기 시작한다. 예를 들어, DFS로 이동할 경우 시작 위치에서 목표 위치까지 한 방향으로 쭉 이동하게 된다. 목표 위치에 도달할 수는 있지만, 이 경우에는 다른 방향에서 더 빠른 경로가 있어도 일단 현재 경로를 끝까지 탐색하게 된다. 예를 들어, 수빈이가 한 경로를 통해 17초에 목표 위치에 도달했더라도, 실제로는 다른 경로로 5초 만에 도달할 수 있는 경우가 있다. DFS는 이 짧은 경로를 우선적으로 탐색하지 않으므로 최단 경로를 보장하지 않으며, 모든 경로를 탐색해야 할 수도 있어 탐색 시간이 길어진다. 이런 특성 때문에 최단 거리를 찾는 문제에는 DFS가 적합하지 않다.

 

반면 BFS는 한 단계씩 모든 가능한 위치를 동시에 탐색해 나가므로, 시작 위치에서 가까운 위치들을 먼저 모두 탐색한 후, 점차 멀리 있는 위치들을 탐색하게 된다. 예를 들어, 수빈이가 위치 5에서 시작했다면, BFS는 5에서 4, 6, 10 위치로 동시에 이동한 뒤, 이들 위치에서 다시 가능한 위치로 이동한다. 이렇게 하면, 목표 위치에 처음 도달한 경로가 가장 짧은 경로임을 보장할 수 있다. 즉, BFS는 목표 위치에 도달했을 때 그 경로가 최단 경로임을 보장하므로 추가 탐색 없이 바로 결과를 반환할 수 있다.