자바 코딩테스트 강좌, 가장 빠른 버스 노선 구하기

이번 글에서는 자바를 사용하여 코딩 테스트에서 출제될 수 있는 “가장 빠른 버스 노선 구하기” 문제를 다루어 보겠습니다. 버스를 이용한 최단 경로 문제는 그리디 알고리즘과 그래프 이론의 기본 개념을 익힐 수 있는 훌륭한 예제입니다. 이를 통해 알고리즘 문제 해결 능력을 향상시키고 자바 코딩 능력을 키워보도록 하겠습니다.

문제 설명

주어진 도시 A와 도시 B 사이에 여러 개의 버스 노선이 있으며, 각 버스 노선은 특정 시간에 출발하여 특정 시간에 도착하는 정보를 가지고 있습니다. 버스 노선은 상이한 소요 시간과 요금을 가지고 있고, 수 많은 노선 중에서 가장 빠른 노선을 선택해야 합니다.

입력

입력은 다음과 같은 형식으로 주어집니다:

  • 첫 번째 줄에 도시 A와 도시 B의 정보를 받습니다.
  • 두 번째 줄에 각 버스 노선의 수 N이 주어집니다.
  • 이어지는 N개의 줄에는 각각의 버스 노선의 시작 도시, 도착 도시, 소요 시간, 요금이 주어집니다.

출력

가장 빠른 버스에 대한 소요 시간을 출력합니다. 만약 도착할 수 없는 경우 “도착할 수 없습니다.”라고 출력합니다.

예제

    입력:
    A B
    3
    A B 5 3000
    A B 3 2500
    B A 2 1500

    출력:
    3

문제 풀이 과정

1. 문제 이해

가장 먼저 해야 할 일은 문제를 철저히 이해하는 것입니다. 노선이 여러 개 존재하며, 각 노선마다 출발지와 도착지, 소요 시간, 요금이 모두 다르다는 점에 유의해야 합니다. 이 문제는 최단 경로를 찾는 문제로 정리할 수 있습니다. 시작 도시 A에서 도착 도시 B로 가는 최단 경로를 찾아야 합니다.

2. 알고리즘 선택

이 문제를 풀기 위해 가장 적합한 알고리즘은 다익스트라(Dijkstra)의 최단 경로 알고리즘입니다. 이는 가중 그래프에서 두 정점 간의 최단 경로를 찾아주는 효율성이 높은 알고리즘으로, 여기서의 가중치는 소요 시간을 나타냅니다. 또한, 자바를 사용해서 구현할 수 있습니다.

3. 다익스트라 알고리즘 구현

다음은 자바로 다익스트라 알고리즘을 구현하는 과정입니다. 먼저, 필요한 클래스를 정의하고, 각 도시와 노선 정보를 저장하기 위한 자료구조를 설정하겠습니다.

    import java.util.*;

    public class BusRoute {
        static class Route {
            String destination;
            int time;
            int price;

            public Route(String destination, int time, int price) {
                this.destination = destination;
                this.time = time;
                this.price = price;
            }
        }

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String start = sc.nextLine(); // 출발지
            String end = sc.nextLine();   // 도착지
            int N = sc.nextInt();         // 노선 수
            Map> graph = new HashMap<>();

            for (int i = 0; i < N; i++) {
                String from = sc.next();
                String to = sc.next();
                int time = sc.nextInt();
                int price = sc.nextInt();
                graph.computeIfAbsent(from, k -> new ArrayList<>()).add(new Route(to, time, price));
            }

            // 다익스트라 알고리즘 호출
            int shortestTime = dijkstra(start, end, graph);

            // 결과 출력
            if (shortestTime == Integer.MAX_VALUE) {
                System.out.println("도착할 수 없습니다.");
            } else {
                System.out.println(shortestTime);
            }
        }
    }

4. 다익스트라 알고리즘의 핵심 로직

다익스트라 알고리즘을 구현하기 위해, 우선 우선순위 큐를 사용하여 최단 시간 정보와 도시 정보를 저장합니다. 각 도시에서 연결된 도시를 탐색하면서, 현재까지의 소요 시간이 기록된 배열을 기반으로 업데이트합니다. 다음은 다익스트라 함수 구현입니다.

    public static int dijkstra(String start, String end, Map> graph) {
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(r -> r.time));
        Map minTime = new HashMap<>();

        pq.add(new Route(start, 0, 0)); // 시작 도시 추가
        minTime.put(start, 0);

        while (!pq.isEmpty()) {
            Route current = pq.poll();

            // 도착지에 도달한 경우
            if (current.destination.equals(end)) {
                return current.time;
            }

            // 현재 도시와 연결된 노선 탐색
            for (Route route : graph.getOrDefault(current.destination, Collections.emptyList())) {
                int newTime = current.time + route.time;

                if (newTime < minTime.getOrDefault(route.destination, Integer.MAX_VALUE)) {
                    minTime.put(route.destination, newTime);
                    pq.add(new Route(route.destination, newTime, route.price));
                }
            }
        }

        return Integer.MAX_VALUE; // 도착할 수 없는 경우
    }

5. 코드 설명

위 코드에서 다익스트라 알고리즘은 우선순위 큐를 사용하여 가장 빠른 노선을 우선적으로 검토합니다. 소요 시간이 가장 적은 도시를 선택하고, 해당 도시와 연결된 다른 도시로의 이동을 진행합니다. 새로운 소요 시간이 기존에 기록된 시간보다 짧을 경우, 정보를 업데이트하며 앞으로 탐색을 이어갑니다.

결론

이번 포스트에서는 “가장 빠른 버스 노선 구하기” 문제를 통해 다익스트라 알고리즘을 자바로 구현하는 과정을 살펴보았습니다. 알고리즘 문제를 풀 때는 문제의 본질을 이해하고, 효과적인 알고리즘을 선택하는 것이 중요합니다. 이 예제는 코딩 테스트 준비에 매우 유용하며, 다른 유사한 문제들에서도 적용할 수 있는 기술입니다.

이와 같은 방식으로 복잡한 문제를 단계적으로 쪼개 해결해 나가며, 알고리즘적 사고를 키워나가길 바랍니다. 다음에는 더욱 다양한 알고리즘과 문제 해결 방법을 탐구해보도록 하겠습니다!

© 2023 블로그 작성자