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

Problem 🔒

문제

https://www.acmicpc.net/problem/1504

 

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1

7

---

Approach 1 ⭕ - 다익스트라 3번

1. 경로 구분
   • 경로1 : 1번 정점 - v1 정점 - v2 정점 - N번 정점
   • 경로2 : 1번 정점 - v2 정점 - v1 정점 - N번 정점
   • 두 가지의 경로 중 최단 경로를 출력해야한다.
2. 다익스트라(Dhstr 메서드)
   • 시작 정점(int start)만 인자로 받는 다익스트라 함수를 만들었다.
   • 먼저, 시작 정점의 비용을 0으로 초기화한다. (cost[start]=0)
   • 방문하지 않은 비용배열(cost[])에서 가장 작은 비용을 가지고 있는 정점을 찾는다.
   • 찾은 정점의 간선을 돌면서, 현재 최소비용보다 더 적다면 최소비용을 갱신한다.
3. 최단 경로 구하기
   • 1번 정점에서 시작하는 다익스트라 함수를 돌렸을때, 1번 정점 → v1 정점으로 가는 최단 경로, 1번 정점 → v2 정점으로 가는 최단 경로를 구할 수 있다.
   • v1 정점에서 시작하는 함수를 돌렸을때, v1 → v2로 가는 최단 경로, v1 → N으로 가는 최단 경로를 구할 수 있다.
   • v2 정점에서 시작하는 함수를 돌렸을때, v2 → N으로 가는 최단 경로, v2 → v1으로 가는 최단 경로를 구할 수 있다.
   • 따라서, 3번의 다익스트라 함수를 실행하여 모든 경로의 최단 경로를 구할 수 있다.
4. 출력
   • 만약 그러한 경로가 없다면, 다익스트라 함수 실행 후 결과 값이 Integer.MAX_VALUE이다.
   • 경로가 없다는 결과 값이 나온다면 해당 경로는 갈 수 없으므로 boolean 값을 false로 저장한다.
   • 2가지 경로의 존재 여부에 따라 출력 코드를 작성했다.

Approach 2 ⭕ - 다익스트라 5번

Approach1에서는 많은 중복 코드와 불필요한 조건 및 변수가 많아서 리팩토링 해보았다.

그 과정에서 이전에는 다익스트라 함수를 3번 실행했다면, 5번으로 함수 호출이 증가하였다.

1. 다익스트라 (Dhstr 메서드)
   • 다익스트라 함수의 인자를 시작 정점(int start)과 도착 정점(int end) 2개를 입력받아, 경로가 없을 경우 -1을 반환하도록 처리하여 유효성 검사가 더 간결해졌다.
   • 그리고 다익스트라 실행 전마다 방문배열과 비용배열을 초기화했다면, 다익스트라 함수 내에서 초기화하도록 중복코드를 수정하였다.
   • 모든 정점에 방문했다면, 마지막에 도착 정점의 값(cost[end])을 반환하도록 수정하였다.
2. 최단경로 결과 계산
   • 이전에는 boolean 변수를 따로 선언하여 각각 경로의 유효성을 조건문으로 반복적으로 확인하여 불필요한 조건문이 많았다.
   • 경로가 유효하지 않은 경우를 -1로 처리해 결과 계산을 간결하게 작성하였다.

다익스트라 함수를 적게 실행하는 것이 더 실행시간이 빠를 것 같았는데, 그 반대였다.

불필요한 조건문을 중복으로 확인하는 로직이 더 실행시간을 잡아먹는것 같다. ㅠㅠ

---

Solution 💡

다익스트라 3번(리팩토링 전)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, E, visit[], cost[];
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    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())+1; E = Integer.parseInt(st.nextToken());
        visit=new int[N]; cost=new int[N];
        for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; list.add(new ArrayList<>());}
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(u).add(new int[]{v,c});
            list.get(v).add(new int[]{u,c});
        }
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
        //case1 : 1-v1-v2-N 순으로 방문
        //case2 : 1-v2-v1-N 순으로 방문
        boolean case1 = true; // 경로가 있는지 확인
        boolean case2 = true; // 경로가 있는지 확인
        Dhstr(1);
        int oneTov1 = cost[v1]; if(oneTov1 == Integer.MAX_VALUE) case1=false;
        int oneTov2 = cost[v2]; if(oneTov2 == Integer.MAX_VALUE) case2=false;

        // 방문배열, 비용배열 초기화
        for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; visit[i]=0;}
        Dhstr(v1);
        int v1Tov2 = cost[v2]; if(v1Tov2 == Integer.MAX_VALUE) case1=false;
        int v1ToN = cost[N-1]; if(v1ToN == Integer.MAX_VALUE) case2=false;

        // 방문배열, 비용배열 초기화
        for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; visit[i]=0;}
        Dhstr(v2);
        int v2ToN = cost[N-1]; if(v2ToN == Integer.MAX_VALUE) case1=false;
        int v2Tov1 = cost[v1]; if(v2Tov1 == Integer.MAX_VALUE) case2=false;

        int ans = -1;
        if(case1 && case2){
            ans = Math.min(oneTov1+v1Tov2+v2ToN, oneTov2+v1ToN+v2Tov1);
        }else if(case1){
            ans = oneTov1+v1Tov2+v2ToN;
        }else if(case2){
            ans = oneTov2+v1ToN+v2Tov1;
        }
        System.out.println(ans);

    }

    public static void Dhstr(int start){
        cost[start] = 0;

        while (true){
            int next = -1; // 다음에 방문할 노드 번호
            int d = Integer.MAX_VALUE; // 최소비용
            for(int i=1; i<N; i++){
                if(visit[i]==0 && cost[i]<d){next = i; d = cost[i];} // 다음에 방문할 노드 찾기
            }
            if(next==-1) break; // 더 이상 방문할 노드가 없음
            visit[next] = 1; // 방문 처리
            for(int[] i : list.get(next)){
                // 현재 최소비용보다 비용이 더 적다면 최소비용 갱신
                if(cost[next]+i[1] < cost[i[0]]){
                    cost[i[0]] = cost[next]+i[1];
                }
            }
        }

    }
}

다익스트라 5번(리팩토링 후)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 특정한최단경로 {
    static int N, E, visit[], cost[];
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    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())+1; E = Integer.parseInt(st.nextToken());
        visit=new int[N]; cost=new int[N];
        for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; list.add(new ArrayList<>());}
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(u).add(new int[]{v,c});
            list.get(v).add(new int[]{u,c});
        }
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
        //case1 : 1-v1-v2-N 순으로 방문
        //case2 : 1-v2-v1-N 순으로 방문
        int case1 = -1, case2 = -1;
        int a1 = Dhstr(1,v1), a2 = Dhstr(v1,v2), a3 = Dhstr(v2,N-1),
                b1 = Dhstr(1,v2), b3 = Dhstr(v1,N-1);
        if(a1>=0 && a2>=0 && a3>=0) case1 = a1+a2+a3;
        if(b1>=0 && a2>=0 && b3>=0) case2 = b1+a2+b3;
        System.out.println(case1!=-1&&case2!=-1?Math.min(case1, case2):Math.max(case1, case2));
    }

    public static int Dhstr(int start, int end){
        // 방문배열, 비용배열 초기화
        for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; visit[i]=0;}
        cost[start] = 0;
        while (true){
            int next = -1; // 다음에 방문할 노드 번호
            int d = Integer.MAX_VALUE; // 최소비용
            for(int i=1; i<N; i++){
                if(visit[i]==0 && cost[i]<d){next = i; d = cost[i];} // 다음에 방문할 노드 찾기
            }
            if(next==-1) break;
            visit[next] = 1; // 방문 처리
            for(int[] i : list.get(next)){
                // 현재 최소비용보다 비용이 더 적다면 최소비용 갱신
                if(cost[next]+i[1] < cost[i[0]]){
                    cost[i[0]] = cost[next]+i[1];
                }
            }
        }
        return cost[end]==Integer.MAX_VALUE?-1:cost[end];
    }
}