[백준] 11403: 경로 찾기 JAVA

접근

1. 우선 그래프 문제이므로, 어떤 형태로 저장할지를 결정해야 한다. 이중 ArrayList로 할지, 아니면 단순 이차원 배열로 할지. 이는 사용하는 알고리즘과 문제에서 주어지는 N의 범위에 따라 다르다. 우선 N의 범위는 100 이하로 매우 작기 때문에 단순 배열로 저장해도 된다. 

2. 그래프 중에서 어떤 알고리즘으로 풀 것인가? 문제를 읽어보면 모든 노드 → 모든 노드로 가는 경로를 찾아야한다. 즉, 플로이드 워셜 알고리즘이 적절하다. 그렇기 때문에 간선 정보는 더더욱 배열로 저장해야 한다는 소리가 된다. 

 

위와 같이 생각하고 처음에 코드를 짰는데, 테스트 케이스와 결과가 다르게 나왔었다. 알고보니 3중 for문에서 k, i, j 순이 아니라 i, j, k순서로 했었다. 그런 자세한 부분까지 기억하고 있는 것은 아니라서 오히려 잘못된 부분을 찾기가 더 어려웠던 것 같다. 

 

코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        int[][] graph = new int[n][n];
        
        for(int i = 0;i < n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j < n;j++)
                graph[i][j] = Integer.parseInt(st.nextToken());
        }

        // 플로이드 워셜 알고리즘
        solve(graph, n);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                sb.append(graph[i][j]).append(" ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }

    static void solve(int[][] graph, int n){
        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] == 0 || graph[k][j] == 0) continue;  // 양수 길이 없음
                    graph[i][j] = 1;                    
                }
            }
        }
    }
}