Floyd-Warshall (플로이드-워셜)

들어가며

플로이드-워셜은 "모든 정점 쌍 사이의 최단 경로"를 구하는 대표적인 알고리즘이다. 이 포스팅에서는 백준 11403번 문제를 통해 플로이드-워셜의 본질을 파악하고, 최단 거리가 아닌 "경로 존재 여부" 변형을 다룬다. 단순히 "삼중 for문으로 푼다"는 개념을 넘어서, 왜 k를 가장 바깥 루프에 두는지, 인접 행렬과 그래프 탐색의 차이는 무엇인지, BFS/DFS 대신 플로이드-워셜을 선택하는 기준은 무엇인지 등 구현하며 고민했던 지점들을 공유한다.

---

플로이드-워셜 이란?

모든 정점 쌍의 경로

다음과 같은 그래프가 있다고 하자.

1 -> 2
2 -> 3

Q1. 1에서 3으로 갈 수 있나?

• 직접 확인: graph[1][3] = 0 (간선 없음)
• 간접 확인: 1 -> 2 -> 3 (경로 존재)

플로이드-워셜은 이처럼 "중간 정점을 거쳐서" 갈 수 있는 모든 경로를 찾는다.

핵심 아이디어

i 에서 j 로 가는 경로 = i -> k -> j (k 를 중간 정점으로)

if(i -> k 가능 && k -> j 가능) = i -> j 가능

비교: BFS vs 플로이드-워셜

구분	BFS	플로이드-워셜
목적	한 정점에서 모든 정점	모든 정점 쌍
자료구조	Queue, visited	인접 행렬만
시간 복잡도	$O(V + E) \times V = O(V^3)$	$O(V^3)$
공간 복잡도	$O(V)$	$O(V^2)$
코드 길이	20 줄	3 줄
용도	개별 탐색	전체 경로 계산

언제 사용할까?

플로이드-워셜을 사용하는 경우:

• 모든 정점 쌍의 경로가 필요할 때
• 중간 정점을 거쳐도 되는 문제
• 간단한 구현이 필요할 때

BFS/DFS를 사용하는 경우:

• 특정 정점에서만 탐색하면 될 때
• 경로 자체를 추적해야 할 때
• 그래프가 매우 희소할 때

---

대표 문제

가중치 없는 방향 그래프가 주어졌을 때, 모든 정점 쌍 (i, j) 에 대해 i 에서 j 로 가는 경로가 있는지 구하는 문제다. 플로이드-워셜의 핵심 원리를 가장 단순하게 보여주는 문제다. 최단 거리가 아닌 "경로 존재 여부"로 변형하여, 알고리즘의 본질을 이해할 수 있다.

문제

백준 11403번 경로 찾기

첫인상

"i -> j 간선 있으면 1, 없으면 0?" -> 그럼 입력 그대로 출력하면 되는데? 함정: 문제는 길이가 양수인 경로를 요구한다.

직접 연결 (착각):
graph[1][3] = 0 → 출력 0

경로 존재 (실제):
1 → 2 → 3 경로 존재 → 출력 1

핵심 차이:

• 직접 연결: 인접 행렬 그대로
• 경로 존재: 중간 정점을 거쳐도 됨

---

구현 경험

인접 행렬 vs 그래프 탐색

처음 이 문제를 접했을 때 가장 헷갈렸던 부분이다. "인접 행렬이 2차원 배열이니까 2차원 배열 탐색 아닌가?"

인접 행렬 graph[i][j]:
- 그래프를 "저장"하는 방식 (2차원 배열 맞음)
- graph[1][2] = 1 의미: "정점 1 → 정점 2 간선 존재"

그래프 탐색:
- 그래프를 "순회"하는 방식
- "정점"을 방문하는 것이지, "배열의 칸"을 방문하는 게 아님

격자 탐색 vs 그래프 탐색

구분	격자 탐색 (미로, 섬)	그래프 탐색 (해당 문제)
위치 표현	좌표 (행, 열)	정점 번호
이동 방향	상하좌우, 대각선, ...	인접 행렬 참조
큐 저장	[행, 열]	정점 번호
visited	boolean[][]	boolean[]

// 격자 BFS (미로)
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});  // 좌표
visited[0][0] = true;

while (!queue.isEmpty()) {
    int[] pos = queue.poll();
    int x = pos[0], y = pos[1];

    // 상하좌우
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        // ...
    }
}

// 그래프 BFS (이번 문제)
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);  // 정점 번호
visited[1] = true;

while (!queue.isEmpty()) {
    int current = queue.poll();

    // 인접 행렬 참조
    for (int next = 1; next <= N; next++) {
        if (graph[current][next] == 1) {
            // ...
        }
    }
}

핵심 차이:

• 인접 행렬: 데이터 저장 (2차원)
• 정점 탐색: 이동 경로 (1차원)

플로이드-워셜 구현

for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (graph[i][k] == 1 && graph[k][j] == 1) {
                graph[i][j] = 1;  // OR 연산처럼
            }
        }
    }
}

BFS 구현과 비교

private static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[N];

    // start와 직접 연결된 정점들
    for (int j = 0; j < N; j++) {
        if (graph[start][j] == 1) {
            queue.offer(j);
            visited[j] = true;
            result[start][j] = 1;
        }
    }

    // BFS 탐색
    while (!queue.isEmpty()) {
        int current = queue.poll();

        for (int next = 0; next < N; next++) {
            if (graph[current][next] == 1 && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                result[start][next] = 1;
            }
        }
    }
}

// 모든 정점에 대해 실행
for (int i = 0; i < N; i++) {
    bfs(i);
}

구분	플로이드-워셜	BFS
기본 개념	중간 정점을 점진적으로 추가하며 모든 경로 계산	시작 정점에서 레벨별로 탐색
자료구조	인접 행렬만 사용	Queue + visited[]
코드 길이	3줄 (삼중 for문)	20줄 (큐 관리 + 초기화)
시간복잡도	$O(N^3)$	$O(N \times (V + E)) = O(N^3)$
공간복잡도	$O(N^2)$	$O(N^2) + O(N)$
추가 메모리	없음	Queue + visited[]

---

구현시 마주친 점

0-based vs 1-based 인덱싱

// 문제 입력
N = 3
graph[1][1] = 0
graph[1][2] = 1

// 내 코드
int[][] graph = new int[N][N];  // [0..2]
// 입력을 [1..3]으로 받으면 ArrayIndexOutOfBoundsException!

해결:

// 방법 1: 0-based 사용 (채택)
int[][] graph = new int[N][N];
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        graph[i][j] = ...;
    }
}

// 방법 2: 1-based 사용
int[][] graph = new int[N+1][N+1];
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        graph[i][j] = ...;
    }
}

결과 배열 분리

// graph 배열을 직접 수정
for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (graph[i][k] == 1 && graph[k][j] == 1) {
                graph[i][j] = 1;  // 원본 수정
            }
        }
    }
}

문제: 원본 그래프가 변경되어 디버깅 어려움

해결:

// 방법 1: 원본 직접 수정 (채택)
// 이 문제는 결과만 출력하므로 원본 보존 불필요

// 방법 2: 결과 배열 분리
int[][] result = new int[N][N];
// graph를 복사
for (int i = 0; i < N; i++) {
    result[i] = graph[i].clone();
}
// result를 수정

 

---

최종 코드

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

          int N = Integer.parseInt(br.readLine());  
          int[][] graph = new int[N][N];  

          for (int i = 0; i < N; i++) {  
             StringTokenizer st = new StringTokenizer(br.readLine());  
             for (int j = 0; j < N; j++) {  
                graph[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 (graph[i][k] == 1 && graph[k][j] == 1) {  
                      graph[i][j] = 1;  
                   }  
                }  
             }  
          }  

          for (int i = 0; i < N; i++) {  
             for (int j = 0; j < N; j++) {  
                bw.write(graph[i][j] + " ");  
             }  
             bw.write("\n");  
          }  

          bw.flush();  
       }  
    }  
}

 

---

🔗GitHub 저장소

해당 글에 작성된 코드는 아래 GitHub 저장소에서 확인할 수 있다.

- 제출 코드: solution/Main.java
- GitHub 저장소: ps-baekjoon-11403-floyd-warshall