[이코테] 미래도시.java

 문제

- 1번부터 N번까지의 회사 존재

- 1번 회사를 시작으로 K번 회사를 무조건 방문 후 X번 회사에 도달

- 최단거리

 

 

 해설 및 코드

- 해당 문제는 플로이드 와샬로 간단하게 풀 수 있다.

import java.util.Arrays;
import java.util.Scanner;

public class 미래도시 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();

		int[][] map = new int[N + 1][N + 1];
		
		for (int i = 0; i < map.length; i++) {
			Arrays.fill(map[i], 987654321);
		}
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			map[a][b] = 1;
			map[b][a] = 1;
		}
		
		int X = sc.nextInt();
		int K = sc.nextInt();
		
		for (int k = 1; k < N+1; k++) {
			for (int i = 1; i < N+1; i++) {
				for (int j = 1; j < N+1; j++) {
					if(map[i][j] > map[i][k]+map[k][j])
						map[i][j] = map[i][k] + map[k][j];
				}
			}
		}
		
		if(map[1][K] == 987654321 || map[K][X] == 987654321)
			System.out.println(-1);
		else
			System.out.println(map[1][K] + map[K][X]);
	}
}

- 만약 도달하지 못하면 -1을 출력

- 플로이드와샬의 포인트는 모든 배열의 초기화를 987654321로 해둬야한다는 것이다.
Integer.MAX_VALUE 사용 시, +를 하게 되면 더 낮은 숫자가 나오게 되기 때문