[JAVA] Floyd-Warshall 플로이드-워셜 / 백준 11404

플로이드-워셜(Floyd-Warshall) 알고리즘이란?

가중 그래프에서 최단 거리를 구할 때 사용하는 알고리즘이다
아래 그래프를 보자

2에서 3으로 갈때 가능한 거리는
2 -> 3, 거리 = 3
2 -> 1 -> 3, 거리 = 4 - 2 = 2
최단 거리는 2 -> 1 -> 3 으로 가는 2다

만약 다른 노드 끼리의 거리를 구하려면?
위 그래프는 눈대중으로 바로 알 수 있지만 복잡해질 경우 찾는데 오래걸린다

플로이드-워셜을 이용해 접근해보자

위 이미지에서 k 값은 중간 노드다
k가 0 부터 4까지 값이 있는데 이는 중간 노드가 없을 때, 노드1일 때 노드2일 때 노드3일 때 노드4일 때를 나눠서 두 노드 사이에 중간 노드가 존재할 경우 중간 노드를 거칠 경우와 안걸칠 경우 중 최단 거리를 업데이트 해가면서 최종적으로 최단 거리를 찾는다 (이 때 거리를 저장할 때 DP를 이용한다)

마지막으로 k 값(중간 노드)을 0부터 4까지 바꿔가면서 최단거리 테이블을 업데이트 한다

노드가 자기 자신으로 이동하는 것은 거리가 0이다
두 노드가 이어지지 않는다면 거리를 무한대로 둔다(거리의 최대값을 넘어가는 값으로 설정하면 됨)

이를 자바 코드로 구현해보자

구현

11404번: 플로이드

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가

www.acmicpc.net

백준에 플로이드를 이용해 구현하는 문제가 있다

우선 코드 전문이다

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

public class Main {

  private static final int INPUT_MAX = 10000001;

  public static void main(String[] args) throws Exception {
    Main.start();
  }

  private static void start() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int m = Integer.parseInt(br.readLine());

    // given
    int[][] arr = new int[n + 1][n + 1];
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (i == j) {
          arr[i][j] = 0;
          continue;
        }
        arr[i][j] = INPUT_MAX;
      }
    }

    for (int i = 0; i < m; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int c = Integer.parseInt(st.nextToken());
      arr[a][b] = Math.min(arr[a][b], c);
    }



    // when
    // 플로이드 와샬 알고리즘 적용
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
        }
      }
    }

    // then
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (arr[i][j] == INPUT_MAX) {
          sb.append("0").append(" ");
          continue;
        }
        sb.append(arr[i][j]).append(" ");
      }
      sb.append("\n");
    }

    System.out.println(sb);
  }
}

1. 초기 그래프를 인접 행렬로 구현

배열을 이용해 초기 거리값들을 담은 인접행렬을 만든다

int[][] arr = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= n; j++) {
    if (i == j) {
      arr[i][j] = 0;
      continue;
    }
    arr[i][j] = INPUT_MAX;
  }
}

배열을 경로상 가능한 값 최대값 이상으로 초기화 해준다
(해당 문제에서는 100 * 100000이 최대값이기 때문에 10000001으로 INPUT_MAX를 설정했다)

2. 거리 가중치 입력 받기

for (int i = 0; i < m; i++) {
  StringTokenizer st = new StringTokenizer(br.readLine());
  int a = Integer.parseInt(st.nextToken());
  int b = Integer.parseInt(st.nextToken());
  int c = Integer.parseInt(st.nextToken());
  arr[a][b] = Math.min(arr[a][b], c);
}

동일 경로가 존재할 경우 더 작은 값으로 입력받으면 된다

3. 플로이드-워셜 적용

for (int k = 1; k <= n; k++) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
    }
  }
}

중간 노드를 바꿔가면서 (k)
저장된 경로와 중간 노드를 거친 경로를 비교한다
여기서 반복문을 무조건 세 번 실행하므로 시간 복잡도는 최악과 최선 모두 Q(N^3)이다

4. 출력하기

StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= n; j++) {
    if (arr[i][j] == INPUT_MAX) {
      sb.append("0").append(" ");
      continue;
    }
    sb.append(arr[i][j]).append(" ");
  }
  sb.append("\n");
}

System.out.println(sb);

INPUT_MAX값은 갈 수 없는 경로이기 때문에 0으로 바꾼다는 것만 주의해서 출력하면 된다

저작자표시

코딩일기