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

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

 

1504번: 특정한 최단 경로

1504번: 특정한 최단 경로

해결 방법

처음에 u, v만 거쳐가면 된다라고 생각해서, 단순하게 start -> u -> v -> end이렇게 가는 최단경로를 구하면 되겠네! 라고 생각했습니다.ㅎㅎ

하지만, u와 v를 거쳐 가라고만 했지 u -> v 이런 순서로 가라고 한적은 없었습니다.😭
따라서 u -> v, v -> u 인 2가지 경우를 고려해야 합니다.

저는 다익스트라(dijkstra)알고리즘을 사용해서 최단 경로를 구했습니다.

• 최단 경로1: start -> u -> v -> end
• 최단 경로2: start -> v -> u -> end

최단 경로1과 최단 경로2를 비교하여 작은 값을 출력 하면 됩니다.^^

 

2023.04.02 - [0 + 알고리즘(Algorithm)] - [알고리즘] 다익스트라(백준 1238, 1753, 1916, 4485 -Java)

[알고리즘] 다익스트라(백준 1238, 1753, 1916, 4485 -Java)

 

풀이

public class Quiz1504 {

    static int INF = 200_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 정점 갯수
        int n = Integer.parseInt(st.nextToken());
        // 간선 갯수
        int e = Integer.parseInt(st.nextToken());

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

        // 그래프 생성
        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 weight = Integer.parseInt(st.nextToken());

            // 양방향
            list[start].add(new Node(end, weight));
            list[end].add(new Node(start, weight));
        }

        // 반드시 거쳐야하는 두점
        st = new StringTokenizer(br.readLine());
        int stopOver1 = Integer.parseInt(st.nextToken());
        int stopOver2 = Integer.parseInt(st.nextToken());

        // start -> stopOver1 -> stopOver2 -> end 경로
        int case1 = 0;
        // 시작점(start)에서 stopOver1 까지 최단 거리
        case1 += dijkstra(list, 1, stopOver1, n);
        // stopOver1에서 stopOver2 까지 최단 거리
        case1 += dijkstra(list, stopOver1, stopOver2, n);
        // stopOver2에서 n 까지 최단 거리
        case1 += dijkstra(list, stopOver2, n, n);
        if(case1 >= INF) {
            System.out.print(-1);
            br.close();
            return;
        }

        // start -> stopOver2 -> stopOver1 -> end 경로
        int case2 = 0;
        // 시작점(start)에서 stopOver2 까지 최단 거리
        case2 += dijkstra(list, 1, stopOver2, n);
        // stopOver2에서 stopOver1 까지 최단 거리
        case2 += dijkstra(list, stopOver2, stopOver1, n);
        // stopOver1에서 n 까지 최단 거리
        case2 += dijkstra(list, stopOver1, n, n);
        if(case2 >= INF) {
            System.out.print(-1);
            br.close();
            return;
        }

        // 최소 거리 비교
        int min = Math.min(case1, case2);
        System.out.print(min);
        br.close();
    }

    private static int dijkstra(List<Node>[] list, int start, int end, int n) {
        // 최단거리 저장 배열 초기화
        int[] result = new int[n+1];
        for(int i = 1; i <= n; i++) {
            result[i] = INF;
        }

        // 시작점 설정
        result[start] = 0;

        // 가중치를 기준으로 올림차순 우선순위큐 생성
        Queue<Node> pq = new PriorityQueue<>(
                (o1, o2) -> Integer.compare(o1.getWeight(), o2.getWeight())
        );
        // 큐에 출발 노드 정보 삽입
        pq.add(new Node(start, result[start]));

        // 방문 이력 배열
        boolean[] visited = new boolean[n+1];

        while (!pq.isEmpty()) {
            Node poll = pq.poll();
            // 방문 이력이 없으면
            if(!visited[poll.getNode()]) {
                visited[poll.getNode()] = true;
                for(Node node : list[poll.getNode()]) {
                    // 최단 거리 계산
                    // min(현재 최단거리 + 해당 노드로 갔을 때 가중치, 해당 노드의 최단 거리)
                    result[node.getNode()] = Math.min(result[poll.getNode()] + node.getWeight(), result[node.getNode()]);
                    pq.add(new Node(node.getNode(), result[node.getNode()]));
                }
            }
        }

        return result[end];
    }

    static class Node {
        private int node;
        private int weight;

        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }

        public int getNode() {
            return node;
        }

        public int getWeight() {
            return weight;
        }
    }
}