[백준] 1504번: 특정한 최단 경로 (Java)

1. 문제설명

방향성 없는 그래프에서 1번 정점에서부터 N번 정점으로 최단 거리로 이동하려 한다. 한 번 이동했던 정점 또는 간선을 다시 이동할 수 있다. 주어진 두 정점을 반드시 거치면서 최단 경로를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 256MB

 

2. 접근 방식

• Node 객체를 사용하여 정점과 거리 정보를 저장한다.
• 인접리스트 형식(List<Node>[] list)으로 간선 정보를 저장한다. (양방향으로)
• 다익스트라 알고리즘을 사용한다.
  • 우선순위 큐를 사용하여 가장 짧은 경로를 먼저 처리하고, 현재 경로에서 더 짧은 경로를 찾으면 경로 정보를 갱신하는 방식으로 구현한다.
  • 두 가지 경로를 구한다.
    • 1 → v1 → v2 → N
    • 1 → v2 → v1 → N
  • 총 3번의 다익스트라 메서드 호출을 통해 두 가지 경로의 최단 거리를 구한다.
    • 1번 정점에서 시작하여 v1 과 N 정점까지의 최단 거리를 구한다.
    • v1번 정점에서 시작하여 v2과 N 정점까지의 최단 거리를 구한다.
    • v2번 정점에서 시작하여 v1 과 N 정점까지의 최단 거리를 구한다.
• v1, v2 정점을 모두 거치는 경로가 존재하는 경우 N정점의 최단 거리를 출력한다.
  • 아닌 경우 -1 을 출력한다.

 

3. 틀린 이유

기존 코드

static final long INF = Long.MAX_VALUE;

기존 코드에서 INF 값을 Long.MAX_VALUE 으로 설정한 것이 문제가 되었다.

다익스트라 알고리즘에서 경로가 존재하지 않는 경우, 경로를 계산하는 과정에서 INF 값을 더하는 상황이 발생하면 오버플로우가 발생하게 된다.

 

4. 틀린 부분 수정

INF 값을 200,000,000 으로 설정하여 오버플로우 문제를 방지하도록 했다.

문제에 주어진 제한 조건에 따르면, 각 간선의 최대 가중치는 1,000이고, 최대 간선 수 200,000 이므로, 가능한 경로의 최댓값은 200,000,000 을 넘지 않는다. 따라서 INF 값을 200,000,000 으로 설정하면 경로 계산에서 충분히 큰 값으로 사용하면서 오버플로우 없이 처리할 수 있다.

static final int INF = 200000000;

 

5. 최종 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, e; // 정점 개수, 간선 개수
    static int v1, v2; // 반드시 거쳐야 하는 두 개의 정점
    static List<Node>[] list; // 인접리스트 형식으로 그래프 저장
    static int[] dist; // 최단 거리 저장
    static final int INF = 200000000;

    static class Node implements Comparable<Node> {
        int vertex; // 정점
        int distance; // 거리

        public Node(int vertex, int distance) { // 생성자
            this.vertex = vertex;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            // 거리 짧은 순으로 정렬
            if(distance > o.distance) return 1;
            else return -1;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        list = new List[n+1]; // 리스트 초기화
        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }

        dist = new int[n+1]; // 최단 거리 배열 초기화
        Arrays.fill(dist, INF); // 무한대 값으로 초기화

        for(int i=0; i<e; i++) { // 그래프 정보 저장
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());
            // 양방향으로 저장
            list[start].add(new Node(end, distance));
            list[end].add(new Node(start, distance));
        }

        // 반드시 거쳐야 하는 두 정점 저장
        st = new StringTokenizer(br.readLine());
        v1 = Integer.parseInt(st.nextToken());
        v2 = Integer.parseInt(st.nextToken());

        // 두 가지 경로를 구함
        // way1 : 1 → v1 → v2 → N
        // way2 : 1 → v2 → v1 → N
        int way1, way2;
        dijkstra(1); // 1번 정점에서 시작하는 최단 경로 구하기
        way1 = dist[v1]; way2 = dist[v2];
        Arrays.fill(dist, INF); // 무한대 값으로 초기화

        dijkstra(v1); // v1번 정점에서 시작하는 최단 경로 구하기
        way1 += dist[v2]; way2 += dist[n];
        Arrays.fill(dist, INF); // 무한대 값으로 초기화

        dijkstra(v2); // v2번 정점에서 시작하는 최단 경로 구하기
        way1 += dist[n]; way2 += dist[v1];

        if(way1 >= INF && way2 >= INF)
            System.out.println("-1");
        else System.out.println(Math.min(way1, way2));
    }

    static void dijkstra(int start) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        dist[start] = 0; // 시작 위치 최단 거리 0으로 설정
        q.offer(new Node(start, 0)); // 시작 위치 큐에 추가
        boolean[] visited = new boolean[n+1]; // 방문 여부 체크

        while(!q.isEmpty()) {
            Node current = q.poll();

            if(visited[current.vertex]) continue;;
            visited[current.vertex] = true;

            for(Node next : list[current.vertex]) {
                if(dist[next.vertex] > dist[current.vertex] + next.distance) {
                    // 더 짧은 경로를 찾으면 갱신 & 큐에 추가
                    dist[next.vertex] = dist[current.vertex] + next.distance;
                    q.offer(new Node(next.vertex, dist[next.vertex]));
                }
            }
        }
    }
}

 

6. 느낀점 or 기억할 정보

아직 다익스트라 문제에 익숙하지 않아 한 번의 호출로 끝내려는 생각만 해서 적절한 알고리즘 설계하는데 오래걸렸다.

그리고 최단 거리를 구하기 위해 배열을 큰 값으로 초기화 할 때, 문제 조건은 생각하지 않고 무조건 큰 값으로 초기화했는데 이것이 문제를 틀리는 주요 원인이 되었다. 앞으로 문제 조건에 따라 최댓값을 설정하도록 주의해야겠다.