99클럽 코테 스터디 1일차 TIL (플로이드-워셜)

플로이드-워셜 알고리즘

개념

최단 경로를 구하는 알고리즘으로 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다.

다익스트라 알고리즘처럼 단일 정점에서 모든 정점으로의 최단 경로가 아니라, 그래프 내 모든 쌍의 정점에 대해 최단 경로를 찾는 데 주로 사용된다.

작동 원리

정점 간 최단 경로를 점진적으로 갱신하여 찾는다. 이때 경유지 개념을 사용해 최단 경로를 갱신하는 방식으로 탐색한다. 모든 정점 쌍에 대해 최단 경로를 계산하기 때문에, 시간 복잡도가 O(n^3) 이 나오게 된다.

구현 코드 - JAVA

for (int k = 0; k < N; k++) { // 경유지
    for (int i = 0; i < N; i++) { // 출발지
        for (int j = 0; j < N; j++) { // 도착지
            // 그래프 최소값으로 갱신
            // 현재의 이동 비용과 경유지를 거쳤을 때의 이동 비용 중 최소값으로 갱신
            graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]); 
        }
    }
}

문제

BOJ 11403 - 경로 찾기

해결 방법

1. 플로이드-워셜 알고리즘으로 모든 정점에 대해 도달할 수 있는지 확인한다.
2. 도달할 수 있다면 간선을 추가하여 다른 정점이 사용할 수 있도록 값을 추가해준다.
3. 갱신된 그래프를 출력한다.

정답 코드 - JAVA

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[][] arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 양수 경로가 존재하는 경우
                    if (arr[i][j] == 1 || (arr[i][k] == 1 && arr[k][j] == 1)) {
                        arr[i][j] = 1; // i에서 j로 가는 간선 추가하기
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(arr[i][j]).append(" ");
            }
            sb.append("\n");
        }

        bw.write(String.valueOf(sb));
        bw.newLine();
        bw.flush();
    }
}

오늘의 회고

플로이드-워셜 알고리즘에 대해 복습하고 이를 바탕으로 문제에 적용하였다. 처음에 적용했을 땐 새로운 결과 배열을 만들어 해당 배열에 값을 추가하는 방식으로 시도했으나 해당 방법을 사용하면 조건문에서 새로운 배열 또한 검사해야 한다. 따라서 기존의 그래프에 추가하여 값을 갱신하도록 구현하였다.

잘못된 방식

if (arr[i][j] == 1 || (arr[i][k] == 1 && arr[k][j] == 1)) { // ret 배열에 대한 조건문이 추가되어야 정답이 나옴
    ret[i][j] = 1; // 새로운 배열에 i에서 j로 가는 간선 추가하기
}