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

백준 11403 - 경로 찾기

요구사항

• 가중치 없는 방향 그래프에서 모든 정점 쌍 (i, j)에 대해
• i에서 j로 가는 경로가 있으면 1, 없으면 0을 출력하는 문제

접근 방식

플로이드-워셜 로 모든 정점 간 경로 존재 여부를 전파했다.

핵심 아이디어

arr[i][k] == 1 && arr[k][j] == 1
→ i에서 k를 거쳐 j로 갈 수 있으면
→ arr[i][j] = 1

k가 반드시 바깥 반복문이어야 하는 이유

k가 바깥 = k를 징검다리로 추가하면서 경로 확장
→ k=1일 때 1을 거치는 모든 경로 완전히 확정
→ k=2일 때 이미 확정된 정보를 활용해 2를 거치는 경로 확장
→ 순서대로 완전히 확정되면서 전파됨 ✅

k가 안쪽이면 아직 확정 안 된 정보를 참조해서 놓치는 경로 발생 ❌

코드

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().trim());
        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][k] == 1 && arr[k][j] == 1)
                        arr[i][j] = 1;

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                sb.append(arr[i][j]).append(" ");
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

느낀점

• 순위 문제에서 익힌 플로이드-워셜 패턴을 바로 적용할 수 있었다.
• k가 바깥 반복문이어야 한다는 것을 확실히 체득했다.
• 플로이드-워셜은 "k를 징검다리로 추가하면서 경로 확장" 으로 기억하자.