[Algorithm/Java] 백준 11403번 - 경로 찾기

---

https://www.acmicpc.net/problem/11403

---

📌 문제

문제 유형

• 그래프

문제 설명

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다.
• 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다.
• i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다.
• i번째 줄의 i번째 숫자는 항상 0이다.

3
0 1 0
0 0 1
1 0 0

출력

• 총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다.
• 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

1 1 1
1 1 1
1 1 1

🔍 문제 풀이

BFS vs 플로이드

• 이 문제는 다음 두 가지 방식으로 해결할 수 있다.
  • BFS 방식: 각 정점에서 출발하여 도달 가능한 정점을 BFS로 탐색
  • 플로이드–워셜 방식: 모든 정점 쌍 간의 경로 존재 여부를 3중 for문으로 계산

• BFS 방식에서는 각 정점 i에 대해 BFS를 수행하고, 방문 가능한 정점 j를 result[i][j] = 1로 저장한다.
• 플로이드 방식에서는 중간 정점 k를 경유하여 i→j 경로가 가능한지 점화식으로 판별한다.

두 방식 모두 문제를 해결할 수 있지만,
입력 크기 N이 100 이하로 작기 때문에 플로이드 방식이 더 간결하고 빠르게 구현 가능하다.

플로이드 워셜 알고리즘

플로이드–워셜 알고리즘에 대해 간단히 알아보자.

• 모든 정점 쌍 (i, j)에 대해, 중간 정점 k를 하나씩 거쳐 갈 수 있는지 판단하는 알고리즘
• 입력으로 받은 인접 행렬 자체를 직접 수정하면서 경로 정보를 갱신한다.

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;
        }
    }
}

• i → k로 갈 수 있고, k → j로 갈 수 있다면 i → j로도 갈 수 있다는 것을 뜻한다.
• 경유 정점 k를 가장 바깥에 둬야, k까지의 경로 정보가 먼저 반영된 상태에서 i → k → j 경로를 판단할 수 있다.
  • (도시 k를 하나 정한다 → 그 다음에 i→j 사이에 k를 넣어 본다)
• 3중 for문을 통해 모든 (i, j) 쌍을 갱신한다.
• 인접 행렬(graph) 그대로 업데이트하므로 별도의 방문 배열 없이도 처리가 가능하다.
• 시간복잡도: O(N³)

📌 놓친 점

BFS에서 visited 처리 위치

visited[start] = true를 BFS 시작 전에 설정하지 않는 이유는 다음과 같다.

• 모든 정점은 BFS 탐색 과정에서 큐에 넣을 때 visited[i] = true로 처리하면 된다.
• 즉, 시작 정점만 큐에 먼저 넣고, 나머지 정점은 탐색하면서 방문 여부를 판단한다.
  
  
• 만약 시작 정점을 탐색 전에 미리 방문 처리해버리면,
  0 → 1 → 2 → 0 같은 순환 구조에서 자기 자신으로 돌아오는 간접 경로를 놓칠 수 있다.
• 따라서 visited[i] = true는 큐에 넣는 시점 (while문 내부) 에 처리해야 한다.

💻 전체 코드

플로이드–워셜 방식

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }
}

BFS 방식

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

public class Main {
    static int n;
    static int[][] graph;
    static int[][] result;

    public static void bfs(int start){
        boolean[] visited = new boolean[n]; // bfs(i)를 돌릴 때마다 초기화 해야함
        Deque<Integer> dq = new ArrayDeque<>();
        dq.offer(start);

        while(!dq.isEmpty()){
            int current = dq.poll();
            for(int i=0; i<n; i++){
                if(graph[current][i] == 1 && !visited[i]){
                    visited[i] = true;
                    result[start][i] = 1; // start에서 i로 도달 가능(단방향 정보)
                    dq.offer(i);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        graph = new int[n][n];
        result = 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());
            }
        }

        // 각 정점에서 BFS 실행
        for(int i=0; i<n; i++){
            bfs(i);
        }

        // 출력
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }
}