[백준, Java] 23793번, 두 단계 최단 경로 1(다익스트라, 그래프 탐색)

문제 링크

23793번: 두 단계 최단 경로 1

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. N개의 정점을 가지고 있으며 M개의 방향성을 가진 간선이 존재합니다.

2. X → Y → Z, X → Y(x) → Z으로 이동하는 최단거리를 결과로 출력합니다.

3. Z정점에 도달하지 못할 때에는 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. X 정점 기준으로 다익스트라를 통해 Y정점을 지날 때와 지나지 않을 때를 기준으로 최단 거리를 탐색합니다.

 

3. 탐색을 통해 얻은 2가지 경우의 최단 거리를 결과로 출력합니다.

 

 

최단 거리 구하기(다익스트라)

 

다익스트라를 통해서 최단거리를 3번 구하였습니다.

 

1. 출발지  → 중계지

 

출발지  → 중계지  → 도착지으로 방문했을 때의 최단 거리를 구해야 하기 때문에 출발지부터 중계지까지의 최단 거리를 구하였습니다.

 

2. 중계지 → 도착지

 

출발지 → 중계지 → 도착지으로 방문했을 때의 최단 거리를 구해야 하기 때문에 중계지부터 도착지까지의 최단 거리를 구하였습니다.

 

 

3. 출발지 → 도착지 (중계 지점을 지나지 않은 경로)

 

중계지를 지나지 않고 출발지 → 도착지까지 도달하는 최단 거리도 문제에서 요구한 최단 거리를 구해야 합니다.

 

 

❖ 출발지 →  중계지, 중계지 →  도착지의 최단 거리를 구할 때에는 기존 다익스트라랑 동일하게 구현하면 되지만 중계지를 지나지 않는 경우에는 기존 다익스트라에 1가지 내용을 추가하였습니다.

 

출발지와 중계지는 동일할 수 없기 때문에 출발지로부터 중계지까지 도달하려면 최소 1개의 간선을 이용해야 합니다.

→ 즉, 중계지까지의 최소 간선치는 0보다 크다는 것이다.

 

최단 거리를 관리하는 int[] 배열에 대해서 중계지의 값을 0으로 설정하였을 때 0보다 더 작은 간선치로 중계지를 방문하지 못하기 때문에 중계지를 방문하지 못하게 됩니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N	M
6	8

 

X(출발지)	Y(중계지)	Z(도착지)
1	2	6

정점과 간선 정보

 

 

 

 

2. X 정점 기준으로 다익스트라를 통해 Y정점을 지날 때와 지나지 않을 때를 기준으로 최단 거리를 탐색합니다.

 

1. 출발지  → 중계지 : 최단 거리

 

 

정점	1	2	3	4	5	6
최단 거리	0	2	3	5	10	8

 

 

 

2. 중계지 → 도착지 : 최단 거리

정점	1	2	3	4	5	6
최단 거리	7	0	10	3	17	7

 

3. 출발지 → 도착지 (중계 지점을 지나지 않은 경로)

정점	1	2	3	4	5	6
최단 거리	0	0	3	INF	10	8

 

※ 중계지 2번은 지나지 않기 때문에 최단 거리를 0으로 초기화하였습니다. 이 때문에 4를 도착하는 경로가 사라져서 INF으로 표현되는 것을 확인하실 수 있습니다.

 

 

3. 탐색을 통해 얻은 2가지 경우의 최단 거리를 결과로 출력합니다.

 

중계지를 지날 때 : 2(출발지 → 중계지) + 7(중계지 → 도착지) = 9

 

중계지를 지나지 않을 때 : 8(출발지 → 도착지) = 8

 

9 8 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용해서 간선 및 정점의 정보를 띄어쓰기 기준 나누었습니다.
• search를 통해서 각 조건에 대한 최단 거리를 탐색합니다.
• 탐색을 통해 얻은 최단거리를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search 함수는 최단 거리 배열 int[]에 대한 기본값을 설정한 뒤 dijkstra 함수를 통해 최단 거리를 구합니다.
• dijkstra 함수는 다익스트라를 통해서 출발지부터 도착지까지의 최단 거리를 구합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    //간선 정보를 정의하는 클래스
    static class Road{
        int nxtCity,distance;

        public Road(int nxtCity, int distance) {
            this.nxtCity = nxtCity;
            this.distance = distance;
        }
    }
    //다익스트라 진행 중 각 데이터를 정의하는 클래스
    static class Node implements Comparable<Node>{
        int city, distance;
        public Node(int city, int distance) {
            this.city = city;
            this.distance = distance;
        }

        //지금까지 이동한 가중치의 합 기준 오름차순 정렬
        @Override
        public int compareTo(Node o) {
            return this.distance - o.distance;
        }
    }
    //간선 정보 저장하는 리스트
    static List<List<Road>>graph = new ArrayList<>();
    static int n;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        //간선 정보 리스트 초기화
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<>());
        }
        //간선 정보 저장
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Road(b,c));
        }
        st = new StringTokenizer(br.readLine()," ");
        //시작,중계,도착 위치 저장
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        int z = Integer.parseInt(st.nextToken());
        //시작 → 중계 최단 거리 구하기
        int xyDistance = search(x, y, null);
        //중계 → 도착 최단 거리 구하기
        int yzDistance = search(y, z, null);
        //중계 위치를 방문하고 도착 위치에 도달하였을 때 최단 거리 계산
        int visitDistance = (xyDistance == -1 || yzDistance == -1 )? - 1 : xyDistance + yzDistance;
        //중계 위치를 방문하지 않고 도착 위치에 도달하였을 때 최단 거리 계산
        int nonVisitDistance = search(x, z, y);
        //최단 거리 결과 값 BufferedWriter 저장
        bw.write(String.format("%d %d", visitDistance, nonVisitDistance ));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
   //기본 방문처리 이후 다익스트라 탐색으로 최단 거리 구하는 함수 
    static int search(int start, int end, Integer nonVisit){
        int[] distance = new int[n+1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;
        //방문하지 않아야 하는 위치 있을 때 해당 방문하지 않도록 설정
        if(nonVisit != null){
            distance[nonVisit] = 0;
        }
        return dijkstra(start, end, distance);
    }

    //start → end까지 다익스트라를 통해 최단 거리 구하는 함수
    static int dijkstra(int start, int end, int[] distance) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        //다익스트라 진행
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if(distance[cur.city] < cur.distance){
                continue;
            }
            //최단 거리 탐색 완료
            if (cur.city == end) {
                return cur.distance;
            }
            //현재 위치에 연결된 간선 탐색
            for (Road nxt : graph.get(cur.city)) {
                int nxtDistance = cur.distance + nxt.distance;
                //최단 거리로 이동할 수 있는 위치인 경우
                if (distance[nxt.nxtCity] > nxtDistance) {
                    distance[nxt.nxtCity] = nxtDistance;
                    pq.offer(new Node(nxt.nxtCity, nxtDistance));
                }
            }
        }
        //end 위치로 도달하지 못한 경우
        return -1;
    }
}