[백준(JAVA)] 11403번: 경로 찾기

문제

✔ 난이도 - Silver 1

dfs 사용 풀이

설명

플로이드–워셜 알고리즘 문제이다.
아래의 블로그 설명을 참고하였다.
참고 블로그

왜 k가 가장 바깥 루프인지?
플로이드-워셜의 논리는 거쳐가는 노드 $k$를 하나씩 추가하며 지도를 업데이트하는 것
처음엔 0번 노드만 거쳐서 갈 수 있는 길을 찾고, 그다음엔 1번 노드까지 포함해서 거쳐갈 수 있는 길을 찾고... 이런 식으로 확장해 나가는 방식이기 때문이다.

자기 자신으로의 경로
만약 i -> k -> i 경로가 존재한다면 graph[i][i]가 1이 된다.
문제에서 요구한 '최소 한 개 이상의 간선을 거쳐야 한다'는 조건이 이 3중 루프 안에서 자연스럽게 해결됨 (처음에 graph[i][i]가 0이었어도 거쳐가는 길이 생기면 1이 되니까!)

풀이

public class Main {

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

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

        // System.out.println(Arrays.deepToString(graph));

        // 간선 저장 끝

        // 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][j] == 1){
                        continue;
                    }  
                    // i에서 k로 갈 수 있고, k에서 j로 갈 수 있다면?
                    // i에서 j로 갈 수 있다는 뜻! (1로 업데이트)
                    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++){
                sb.append(graph[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}