Algorithm/유형별 문제 풀기
[최단경로] 문제이름 : 미래도시
sw_develop
2022. 1. 11. 18:48
문제 설명
주인공이 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
*/