[백준 26125] 두 도로 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/26125

26125번: 두 도로

 

문제

울산에는 1번부터 N번까지 번호가 붙은 N개의 교차로가 있고, 교차로와 교차로를 잇는 M개의 도로가 있다. 각 도로는 일방통행이며, 도로를 따라 이동하는 데 걸리는 시간이 정해져 있다.

윤이는 매일 현대모비스의 자율주행 시스템을 탑재한 차를 타고 집에서 회사로 출근한다. 윤이의 집은 S번 교차로에, 회사는 T번 교차로에 있다. 현대모비스의 자율주행 시스템은 항상 집에서 회사까지 최단 시간이 걸리는 주행 경로를 이용한다.

윤이는 얼마 전 울산에 새로운 도로 두 개가 건설될 것이라는 계획을 들었다. 윤이는 앞으로 회사에 더 빠르게 출근할 수 있을 거라는 기대감에 부풀어 있다. 하지만 윤이는 새 도로가 어떤 교차로를 잇는지와, 새 도로를 따라 이동하는 데 걸리는 시간이 얼마인지에 대한 내용을 듣지는 못했다. 따라서 윤이는 Q개의 도로 건설 시나리오를 가정하고, 각 상황에서 윤이의 자율주행차가 어떤 경로를 따라 주행할지 계산해 보기로 했다.

윤이가 가정한 Q개의 도로 건설 시나리오 각각에 대해, 윤이가 현대모비스 자율주행 시스템을 이용하여 집에서 회사로 출근하는 데 걸리는 시간을 구하시오.

 

입력

첫 번째 줄에 교차로의 수 N, 기존 도로의 수 M, 집의 교차로 번호 S, 회사의 교차로 번호 T가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300; 0 ≤ M ≤ 3 000; 1 ≤ S ,T ≤ N; S ≠ T)

이후M개의 줄에 기존 도로에 대한 정보를 나타내는 정수 u, v, w가 공백으로 구분되어 주어진다. 시작 교차로가 u번, 도착 교차로가 v번이고 이동하는 데 w의 시간이 걸리는 일방통행 도로를 나타낸다. (1 ≤ u, v ≤N; 1 ≤ w ≤ 10^6)

그 다음 줄에 도로 건설 시나리오의 수 Q가 주어진다. ( 1 ≤ Q ≤100 000)

이후 Q개의 줄에 새로 건설될 두 개의 도로에 대한 정보를 나타내는 정수 a1, b1, c1, a2, b2, c2가 공백으로 구분되어 주어진다. 시작 교차로가 a1번, 도착 교차로가 b1번이고 이동하는 데 c1의 시간이 걸리는 일방통행 도로와, 시작 교차로가 a2번, 도착 교차로가 b2번이고 이동하는 데 c2의 시간이 걸리는 일방통행 도로를 새롭게 건설하는 시나리오를 나타낸다. ( 1 ≤ a1, b1, a2, b2 ≤ N; 1 ≤ c1, c2 ≤ 10^6)

같은 교차로 쌍을 잇는 도로가 여러 개 주어질 수 있으며, 시작 교차로와 도착 교차로가 동일한 도로가 주어질 수 있다.

 

출력

각 도로 건설 시나리오에 대해, 윤이가 집에서 회사로 출근하는 데 걸리는 시간을 Q개의 줄에 걸쳐 출력한다. 만약 어떤 시나리오에서 집에서 회사로 출근하는 것이 불가능하다면, 해당 줄에는 대신 −1을 출력한다.

풀이

접근법

1.  다익스트라라고 생각할 수도 있지만, 모든 점에 대해서 얼마나 걸리는 지에 대해 저장을 해야 하고, N의 범위가 최대 300밖에 되지 않기 때문에 플로이드 워셜을 사용하면 될 것 같다.
2. 어떠한 도로가 2개 생성될 때 경우의 수는 다음과 같다.
   1. 새로운 도로를 사용하지 않는 경우
   2. 첫번째 도로만 사용하는 경우
   3. 두번째 도로만 사용하는 경우
   4. 첫번째 도로 - 두번째 도로 순으로 사용하는 경우
   5. 두번째 도로 - 첫번째 도로 순으로 사용하는 경우
3. 가지 못하는 지점에 대해서는 -1을 출력해야 한다. 이는 N이 300, w가 최대 10^6이라고 할 때 배열의 값을 5억으로 설정하면 4번까지 더해도 정수 범위를 넘어가지 않고, 결과값이 3억을 넘지 않는다는 것을 고려했을 때 조건문으로 따로 빼도 될 것 같다.

 

코드

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

public class Main {
    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 M=Integer.parseInt(st.nextToken());
        int S=Integer.parseInt(st.nextToken());
        int T=Integer.parseInt(st.nextToken());
        
        // 1. 다익스트라라고 생각할 수도 있지만, 모든 점에 대해서 얼마나 걸리는 지에 대해 저장을 해야 하고, 
        // N의 범위가 최대 300밖에 되지 않기 때문에 플로이드 워셜을 사용하면 될 것 같다.
        int[][] arr = new int[N+1][N+1];
        
        // 3-1. 가지 못하는 지점에 대해서는 -1을 출력해야 한다. 
        // 이는 N이 300, w가 최대 10^6이라고 할 때 배열의 값을 5억으로 설정하면 4번까지 더해도 
        // 정수 범위를 넘어가지 않고, 결과값이 3억을 넘지 않는다는 것을 고려했을 때 
        // 조건문으로 따로 빼도 될 것 같다.
        for(int i=0;i<=N;i++) Arrays.fill(arr[i], 500000000);
        for(int i=0;i<=N;i++) arr[i][i] = 0;

        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int u=Integer.parseInt(st.nextToken());
            int v=Integer.parseInt(st.nextToken());
            int w=Integer.parseInt(st.nextToken());
            arr[u][v] = Math.min(arr[u][v], w);
        }

        for(int k=1;k<=N;k++) {
            for(int i=1;i<=N;i++) {
                for(int j=1;j<=N;j++) {
                    if (arr[i][k] == -1 || arr[k][j] == -1) continue;
                    arr[i][j] = Math.min(arr[i][k] + arr[k][j], arr[i][j]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        int Q=Integer.parseInt(br.readLine());
        for(int q=0;q<Q;q++) {
            st = new StringTokenizer(br.readLine());
            int a1 = Integer.parseInt(st.nextToken());
            int b1 = Integer.parseInt(st.nextToken());
            int c1 = Integer.parseInt(st.nextToken());
            int a2 = Integer.parseInt(st.nextToken());
            int b2 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            // 2. 어떠한 도로가 2개 생성될 때 경우의 수는 다음과 같다.
            
            // 새로운 도로를 사용하지 않는 경우
            int ans = arr[S][T];
            // 첫번째 도로만 이용하는 경우
            ans = Math.min(ans, arr[S][a1] + c1 + arr[b1][T]);
            // 두번째 도로만 이용하는 경우
            ans = Math.min(ans, arr[S][a2] + c2 + arr[b2][T]);
            // 첫번째 도로 - 두번째 도로 순으로 사용하는 경우
            ans = Math.min(ans, arr[S][a1] + c1 + arr[b1][a2] + c2 + arr[b2][T]);
            // 두번째 도로 - 첫번째 도로 순으로 사용하는 경우
            ans = Math.min(ans, arr[S][a2] + c2 + arr[b2][a1] + c1 + arr[b1][T]);
            
            // 3-2. 이렇게 조건문으로 5억 이상일 경우 == 가지 못하는 경우로 설정하여
            // -1을 출력하도록 한다.
            if (ans >= 500000000) sb.append("-1\n");
            else sb.append(ans).append("\n");
        }
        System.out.println(sb);

    }
}

 

23분 걸렸다 !