파이썬 코딩테스트 강좌, 타임머신으로 빨리 가기

안녕하세요! 이번 강좌에서는 ‘타임머신으로 빨리 가기’라는 흥미로운 알고리즘 문제를 다루어 보겠습니다. 이 문제는 다양한 데이터 구조와 알고리즘을 활용하여 해결할 수 있으며, 코딩 테스트에서 자주 출제됩니다. 아래에서 문제 설명, 접근 방식, 그리고 코드 구현을 상세히 다루어 보겠습니다.

문제 설명

시간 여행이 가능한 타임머신이 있습니다. 이 타임머신은 특정 시간으로 이동할 수 있는 기능이 있습니다. 그러나 타임머신의 작동을 위해 다음과 같은 조건이 주어집니다:

현재 시간 0에서 시작합니다.
타임머신은 t - 1년 후의 시간으로 이동할 수 있는 능력이 있습니다. 즉, t와 같은 시간이 주어질 경우 t - 1로 이동할 수 있습니다.
주어진 시간 n까지 빠르게 도달하기 위해 최소한의 이동 횟수를 찾아야 합니다.
타임머신의 이동은 다음과 같이 정의됩니다:
- 지금 시간에서 +1 초가 걸리는 직접 이동.
- 타임머신을 통해 t - 1 년으로 이동하는 것이 가능합니다.

입력

정수 n (0 ≤ n ≤ 1,000,000): 도달하고자 하는 목표 시간

출력

시간 n에 도달하는 최소의 이동 횟수를 출력합니다.

접근 방식

이 문제를 해결하기 위해 BFS(Breadth-First Search) 알고리즘을 활용하겠습니다. BFS는 최단 경로를 찾는 데 효과적입니다. 네트워크 그래프의 모든 정점에 고르게 접근하는 성질 덕분에, 현재 위치에서 가능한 모든 이동을 한 번씩 시도해볼 수 있습니다.

BFS를 이용한 접근 방식

현재의 시간이 0부터 시작합니다.
큐를 사용하여 현재의 시간과 이동 횟수를 저장합니다.
큐에서 시간을 꺼내며 두 가지 이동을 시도합니다:
- +1: 현재 시간 + 1
- t - 1: 현재 시간 – 1 (단, 0보다 작지 않도록 검사)
목표 시간이 되면 그 시점의 이동 횟수를 출력합니다.

문제 해결을 위한 알고리즘 구현


from collections import deque

def min_move_to_time(n):
    visited = [False] * (2 * n + 1) # 방문 여부를 저장할 셋
    queue = deque([(0, 0)]) # 시작점 (현재 시간, 이동 횟수)

    while queue:
        current_time, moves = queue.popleft()
        
        # 목표에 도달했는지 확인
        if current_time == n:
            return moves
        
        # 두 가지 이동 시도: +1과 t - 1
        next_pos = current_time + 1
        if next_pos <= 2 * n and not visited[next_pos]:
            visited[next_pos] = True
            queue.append((next_pos, moves + 1))

        next_pos = current_time - 1
        if 0 <= next_pos and not visited[next_pos]:
            visited[next_pos] = True
            queue.append((next_pos, moves + 1))

코드 해석

위의 코드에서, min_move_to_time 함수는 입력으로 주어진 n까지 이동하는 최소 횟수를 반환합니다. 다음은 코드의 구조입니다:

visited 리스트를 사용하여 방문한 시간들을 기록하고 무한히 탐색하지 않도록 합니다.
큐에서 현재 시간과 이동 횟수를 꺼내어, 목표에 도달했는지 확인합니다.
타임머신의 두 가지 이동 방법을 사용하여 다음 시간을 큐에 추가하고, 이때 visited 리스트를 업데이트합니다.

결과 테스트

이제 이 알고리즘을 사용하여 몇 가지 테스트 케이스를 실행해 보겠습니다.


# 테스트 케이스 1
print(min_move_to_time(5))  # 출력: 5

# 테스트 케이스 2
print(min_move_to_time(10)) # 출력: 10

# 테스트 케이스 3
print(min_move_to_time(100)) # 출력: 100

결론

‘타임머신으로 빨리 가기’ 문제는 BFS 알고리즘을 이용하여 최적의 결정을 내리는 과정을 배울 수 있는 좋은 예시입니다. 이를 통해 알고리즘 문제 해결 능력을 한층 더 키울 수 있습니다. 여러분의 코딩 테스트에 좋은 결과가 있기를 바랍니다!