안녕하세요! 오늘은 C#을 이용한 알고리즘 문제풀이 강좌를 진행하겠습니다. 주제로는 ‘타임머신으로 빨리 가기’입니다. 해당 문제는 코딩테스트에서 자주 접할 수 있는 DFS(Depth First Search)와 BFS(Breadth First Search)의 혼합 문제로, 최단 경로를 찾는 것이 주된 목표입니다.
문제 설명
당신은 시간 여행을 할 수 있는 기능이 있는 타임머신을 가지고 있습니다. 당신의 목표는 현재 시간에서 미래의 특정 시간으로 이동하는 것입니다. 그러나 타임머신은 다음과 같은 규칙이 있습니다:
- 현재 시간이 X일 때, X – 1 초로 이동하면 1초 후로 이동합니다.
- 현재 시간이 X일 때, X + 1 초로 이동하면 1초 후로 이동합니다.
- 현재 시간이 X일 때, X * 2 초로 순간 이동할 수 있습니다.
당신은 현재 시간 0초에 있으며, N초 후에 도착해야 합니다. 타임머신을 이용하여 N초를 가장 빠르게 도달하는 방법을 계산하세요.
입력 형식
입력은 한 줄로 구성되어 있으며, 목표 시간 N이 주어집니다. (0 ≤ N ≤ 100,000)
출력 형식
가장 빠르게 도달하는 방법으로 걸리는 시간을 출력합니다.
문제 예제
입력:
5
출력:
5
문제 풀이 접근법
이 문제는 BFS를 통해 해결할 수 있습니다. BFS는 최단 경로를 찾는 데 매우 효과적이며, 모든 가능한 경로를 탐색하면서 최적의 해를 찾을 수 있습니다. BFS를 사용할 때는 Queue를 사용하여 현재 상태를 저장하고, 다음 상태를 큐에 추가하는 방식으로 진행합니다.
1단계: BFS 구조 이해하기
BFS는 다음과 같은 구조로 진행됩니다:
- 현재 위치를 큐에 추가합니다.
- 큐에서 위치를 꺼내고, 그 위치에 도달하기 위해 필요한 시간을 저장합니다.
- 현재 위치에서 가능한 모든 이동을 계산합니다.
- 이동한 새로운 위치가 목표 위치(N)와 같으면 종료합니다.
- 아니면 이동한 위치를 체크하고 큐에 추가합니다.
2단계: C# 코드 구현
코드를 구현하여 BFS를 통해 이를 해결해보겠습니다:
using System;
using System.Collections.Generic;
public class TimeMachine
{
public static void Main(string[] args)
{
int targetTime = int.Parse(Console.ReadLine());
Console.WriteLine(FindMinimumTime(targetTime));
}
public static int FindMinimumTime(int target)
{
Queue queue = new Queue();
bool[] visited = new bool[100001];
queue.Enqueue(0); // 시작 시간
visited[0] = true;
int[] timeArray = new int[100001]; // 각 인덱스에 도달하는 데 걸리는 시간을 저장
while (queue.Count > 0)
{
int currentTime = queue.Dequeue();
if (currentTime == target)
{
return timeArray[currentTime];
}
// 이동: X - 1
if (currentTime - 1 >= 0 && !visited[currentTime - 1])
{
queue.Enqueue(currentTime - 1);
visited[currentTime - 1] = true;
timeArray[currentTime - 1] = timeArray[currentTime] + 1; // 이동 시간 추가
}
// 이동: X + 1
if (currentTime + 1 <= 100000 && !visited[currentTime + 1])
{
queue.Enqueue(currentTime + 1);
visited[currentTime + 1] = true;
timeArray[currentTime + 1] = timeArray[currentTime] + 1; // 이동 시간 추가
}
// 이동: X * 2
if (currentTime * 2 <= 100000 && !visited[currentTime * 2])
{
queue.Enqueue(currentTime * 2);
visited[currentTime * 2] = true;
timeArray[currentTime * 2] = timeArray[currentTime] + 1; // 이동 시간 추가
}
}
return -1; // 도달할 수 없는 경우
}
}
3단계: 코드 설명
각 부분에 대해 자세히 설명하겠습니다:
Queue와 배열
Queue는 BFS의 핵심 데이터 구조로, 현재 위치를 유지하는 데 사용됩니다. visited 배열은 이미 확인한 시간을 기록하여 무한 루프에 나가지 않도록 방지하고, timeArray는 각 시간에 도달하기 위한 최소시간을 저장합니다.
이동 로직
이동 로직은 현재 시간에서 X-1, X+1, X*2 로 각각 이동 가능한지 검사합니다. 이때 만약 이 위치가 이미 방문했다면 큐에 추가하지 않습니다.
최종 목표 확인
현재 시간과 목표 시간이 동일하다면 BFS를 종료하고, 그때까지 소요된 시간을 반환합니다. 이를 통해 우리는 최단시간에 목표 시간에 도착할 수 있습니다.
결론
이 문제는 BFS를 활용하여 그래프 탐색을 수행하는 대표적인 예제입니다. 코딩테스트에서 자주 출제되므로 이해하고 활용하는 것이 중요합니다. 구현 과정을 통해 BFS에 대한 실력을 다지셨길 바랍니다. 다음 시간에도 더 흥미로운 알고리즘 문제로 찾아뵙겠습니다!
감사합니다!