백준 BOJ 1389번

---

접근 방법

 

그래프에서 정점간에 최단 경로를 구하는 문제다. 

BFS를 사용해도 되지만 , 이전에 두 번정도 해봤으니 이번에는 플로이드 와샬 알고리즘을 알아보자.

 

플로이드-와샬

최단 경로 알고리즘 중 하나로, 모든 정점 간 최단 경로를 구하는 알고리즘이다.

보통은 간선의 가중치가 있지만, 이번 문제는 따로 가중치가 없다. (그래서 BFS로도 풀 수 있음)

하지만 가중치가 있는게 이해하기 쉬우니까 가중치가 있는걸 예로 들겠다.

 

Step 1

그래프를 2차원 인접 행렬로 구성한다.

출처 : https://chanhuiseok.github.io/posts/algo-50/

초기 그래프를 인접행렬로 나타내면 다음과 같다. INF는 길이 없다는 뜻.

	1	2	3	4	5
1	0	5	INF	9	1
2	INF	2	0	INF	INF
3	INF	2	0	7	INF
4	9	INF	7	0	2
5	1	INF	INF	2	0

 

Step 2

중간 노드로 사용할 노드를 설정하고, 최단거리를 갱신한다.

순서대로 1번 노드를 중간 노드로 설정하고 그래프를 갱신해보자. 예를 들면 2에서 4으로 가는 간선이 없었지만, 1을 중간 노드로 설정했기 때문에 2 → 1 → 4 로 길이 생기면서 그래프의 값이 갱신된다. 값은 5 + 9 = 14.

	1	2	3	4	5
1	0	5	INF	9	1
2	5	0	2	14	6
3	INF	2	0	7	INF
4	9	14	7	0	2
5	1	6	INF	2	0

 

Step 3

Step 2를 노드 개수만큼 반복한다.

단계마다 중간 노드를 설정하고 각 노드마다 최단경로를 갱신한다. 노드 개수만큼 반복한다. 예시에서 노드가 5개까지 있으므로 5단계까지 반복하면 된다.1번을 중간 노드로 설정했으니 다음은 2번노드를 중간 노드로 설정하면 된다.

	1	2	3	4	5
1	0	5	7	9	1
2	5	0	2	14	6
3	7	2	0	7	8
4	9	14	7	0	2
5	1	6	8	2	0

2단계를 끝낸 그래프.

---

코드

import java.util.*;

public class Main {
   static int MAX = 1000;
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int N = in.nextInt();
      int M = in.nextInt();
      int rel[][] = new int[N+1][N+1];
      boolean visit[] = new boolean[N+1];

      for(int i = 1; i <= N; i++){
         for(int j = 1; j <= N; j++){
            rel[i][j] = MAX;
            if(i == j) rel[i][j] = 0;
         }
      }
      for(int i = 0; i < M; i++){
         int x = in.nextInt();
         int y = in.nextInt();
         rel[x][y] = 1;
         rel[y][x] = 1;
      }

      for(int k = 1; k <= N; k++){
         for(int j = 1; j <= N; j++){
            for(int i = 1; i <= N; i++){
               if(rel[i][j] > rel[i][k] + rel[k][j])
                  rel[i][j] = rel[i][k] + rel[k][j];
            }
         }
      }
      int sum;
      int min = MAX;
      int id = 0;
      for(int i = 1; i <= N; i++){
         sum = 0;
         for(int j = 1; j <= N; j++){
            sum += rel[i][j];
         }
         if(min > sum) {
            min = sum;
            id = i;
         }
      }
      System.out.println(id);
      in.close();
   }
}