[최단경로] 문제이름 : 미래도시

문제 설명

주인공이 1  → K → X 로 가는데 걸리는 최소 시간을 계산하는 프로그램을 작성하시오.

 

입력 조건

→ 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다. (1 <= N, M <= 100)

→ 둘째 줄부터 M+1 번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.

→ M+2 번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다. (1 <= K <= 100)

 

출력 조건 

→ K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.

→ 만약 X번 회사에 도달할 수 없다면 -1을 출력한다.

 

사용 개념

그래프, 최단경로 알고리즘

 

문제 해결 아이디어 

우선, 문제에서 '주어진 곳으로 가는 최소 시간'을 계산하라고 하였으므로, 최단경로 문제이다.

 

이때 입력 조건에서 주어지는 값들은 

→ 회사의 개수 N = 노드의 개수, 경로의 개수 M = 간선의 개수

→ 연결된 두 회사의 번호 = 간선으로 이어진 두 노드

를 의미한다.

 

최단경로 알고리즘은 1. 다익스트라, 2. 플로이드 워셜로 구현할 수 있는데,

주어진 조건에서 노드의 개수가 최대 100개 이므로 플로이드 워셜을 사용할 수 있다. (다익스트라보다 구현이 간단함)

 

 

코드 

import java.util.*;

public class Main {

    public static int INF = (int) 1e9;

    public static int numOfNode, numOfEdge;

    // 2차원 배열로 그래프 표현 (그래프 겸 최단 거리 테이블)
    public static int[][] graph = new int[101][101]; // 문제 조건에서 노드의 개수 <= 100

    public static void main(String[] args){
        Scanner kbd = new Scanner(System.in);

        numOfNode = kbd.nextInt();
        numOfEdge = kbd.nextInt();

        // 2차원 배열 - 무한으로 초기화
        for(int i = 0; i <= numOfNode; i++){
            Arrays.fill(graph[i], INF);
        }

        // 2차원 배열 - 자기 자신으로 가는 경로에 대해서는 0으로 설정
        for(int i = 1; i <= numOfNode; i++){
            for(int j = 1; j <= numOfNode; j++){
                if(i == j) graph[i][j] = 0;
            }
        }

        // 2차원 배열 - 노드 간의 관계 채우기
        for(int i = 0; i < numOfEdge; i++){
            int a = kbd.nextInt();
            int b = kbd.nextInt();
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        int x = kbd.nextInt();
        int k = kbd.nextInt();

        // 플로이드 워셜
        for(int i = 1; i <= numOfNode; i++){
            for(int a = 1; a <= numOfNode; a++){
                for(int b = 1; b <= numOfNode; b++){
                    graph[a][b] = Math.min(graph[a][b], graph[a][i] + graph[i][b]);
                }
            }
        }

        int result = graph[1][k] + graph[k][x];
        if(result >= INF) System.out.println(-1);
        else System.out.println(result);
    }

}

/*
[Input Example]
5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5
[Output Example]
3
*/