이 글에서는 자바 언어를 이용한 코딩 테스트 준비 방법과 함께, 실제 알고리즘 문제를 풀어보는 과정을 다루겠습니다. 주제는 ‘타임머신으로 빨리 가기’입니다. 이 문제를 통해 그래프 탐색 기법과 알고리즘 최적화를 배우고, 어떻게 문제를 분석하고 해결하는지 알아보겠습니다.
문제 설명
타임머신을 타고 과거와 미래를 오갈 수 있는 여행을 하고 있습니다. 타임머신은 다음과 같은 조건에서 과거로 갈 수 있습니다:
- 현재 위치에서 1초 후에 한 칸 앞으로 이동
- 현재 위치에서 2초 후에 한 칸 뒤로 이동
당신의 목표는 Z초 후에 X좌표에 도착하는 것입니다. 타임머신을 사용하는 최소 시간을 구하세요.
입력 형식
정수 X, Z (-10^6 ≤ X ≤ 10^6, 0 ≤ Z ≤ 10^6)출력 형식
타임머신을 사용하는 최소 시간. 불가능할 경우 -1을 출력예시
입력:
출력:
5 7출력:
7
입력:
출력:
2 5출력:
-1
문제 풀이 과정
이 문제를 풀기 위해서는 목표하는 위치 X에 도달하기 위해 타임머신의 사용 조건을 이해하고, 이를 기반으로 BFS(너비 우선 탐색) 알고리즘을 적용하는 것이 효과적입니다. BFS는 주어진 조건에서 최단 경로를 찾는 데 유리한 알고리즘입니다.
1단계: 상태 정의
타입머신의 각각의 상태를 표현하기 위해 현재 위치와 경과 시간를 사용합니다.
2단계: 이동 규칙 정의
- 한 칸 앞으로 이동:
현재 위치 + 1 - 한 칸 뒤로 이동:
현재 위치 - 1
3단계: BFS 구현
import java.util.*;
public class TimeMachine {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int X = sc.nextInt();
int Z = sc.nextInt();
System.out.println(minimumTime(X, Z));
}
public static int minimumTime(int target, int z) {
Queue queue = new LinkedList<>();
Set visited = new HashSet<>();
queue.add(new int[]{0, 0}); // {현재 위치, 경과 시간}
while (!queue.isEmpty()) {
int[] current = queue.poll();
int position = current[0];
int time = current[1];
if (time > z) continue; // Z 초가 넘어가면 무시
if (position == target && time == z) return time;
// 한 칸 앞으로 이동
if (!visited.contains(position + 1)) {
queue.add(new int[]{position + 1, time + 1});
visited.add(position + 1);
}
// 한 칸 뒤로 이동
if (!visited.contains(position - 1)) {
queue.add(new int[]{position - 1, time + 2});
visited.add(position - 1);
}
}
return -1;
}
} 4단계: 테스트 및 최적화
위 코드를 작성한 후 다양한 입력값을 넣어 테스트해 보세요. 불가능한 경우도 잘 처리하는지 확인해야 합니다. 또한, 메모리 사용량이나 실행 시간을 최적화하는 방법도 고민해 보십시오.
마무리
이번 강좌에서는 자바를 이용하여 알고리즘 문제를 슬기롭게 해결하는 방법에 대해 알아보았습니다. ‘타임머신으로 빨리 가기’ 문제를 통해 BFS 알고리즘의 기초와 상태 공간 탐색의 효과성을 경험했습니다. 지속적으로 다양한 문제를 해결하며 실력을 쌓아가길 바랍니다.