최단 경로 - 플로이드 워셜 Floyd warshall

kayla·2024년 9월 21일
0

그래프

목록 보기
4/4

백준 11403

플로이드 워셜 Floyd warshall

"모든 노드" 간에 최단 경로 탐색
음수 가중치 에지가 있어도 수행할 수 있음(음수사이클X)
동적 계획법의 원리를 이용해 알고리즘에 접근
시간복잡도 O(V^3) - 꽤 느림(N=1000 X)
오히려 N이 작을 때 플로이드 워셜 고려

핵심 이론

A->K->B가 최단 경로면 A->K, k->B도 최단 경로이다.

플로이드 워셜 구현 방법

= 3중 for문

실질적으로 최단 경로 배열 D[][] 하나만 구현

  1. 인접 행렬을 선언하고 자기 자신만 0, 나머지는 무한대로 초기화
    (플로이드 워셜은 노드 개수 적으니까 인접 행렬)
  2. 최단 경로 배열 D[][] 에 그래프 데이터 저장하기
  3. 3중 for문으로 최단 경로 배열 업데이트하기
    (가장 바깥쪽이 경유지 K, 중간이 출발노드 S, 안쪽이 도착노드 E - 모두 (1~N),
    경유지를 거치는게 더 빠르면 업데이트)

백준 11403

import java.util.*;

public class Main {

	public static int N;
	public static int[][] graph;

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

		int N = sc.nextInt();
		graph = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				graph[i][j] = sc.nextInt();
			}
		}

		for (int k = 0; k < N; k++) {
			for (int s = 0; s < N; s++) {
				for (int e = 0; e < N; e++) {
					if (graph[s][k] + graph[k][e] == 2) {
						graph[s][e] = 1;
					}
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(graph[i][j] + " ");
			}
			System.out.println();
		}

		sc.close();

	}

}
profile
Java 코딩테스트 준비하면서 공부한 내용 올립니다 :D

0개의 댓글

관련 채용 정보