[백준] 11403. 경로 찾기

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

11403번: 경로 찾기

이 문제는 DFS와 플로이드 두 가지 방법으로 풀 수 있다.

 

DFS로 푸는 방법은 다음과 같다.

• 각 정점을 시작으로 이동할 수 있는 다른 정점을 구한다. 이때 dfs를 사용한다.
• dfs의 결과로 visited[] 배열에 값이 채워지는데, 이때 true이면 이동할 수 있는 것이고, false이면 이동할 수 없는 것이다.
• 시간 복잡도는 각 정점을 시작으로 dfs를 시작하므로, O(N * (V + E))이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 시간 복잡도: O(N * (V + E))
public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n;
    static int[][] map;
    static boolean[] visited;
    static int[][] answer;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());
        map = new int[n + 1][n + 1];
        answer = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i <= n; i++) {
            visited = new boolean[n + 1];
            dfs(i); // i를 시작으로 이동할 수 있는 정점 찾기 
            for (int j = 1; j <= n; j++) {
                if (visited[j]) { // visited[j]의 값이 true이면 i에서 j로 이동이 가능한 것임
                    answer[i][j] = 1;
                }
            }
        }

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

    private static void dfs(int start) {
        for (int i = 1; i <= n; i++) {
            if (map[start][i] == 1 && !visited[i]) {
                visited[i] = true; // 방문 처리
                dfs(i); // i를 시작으로 또 이동해보기
            }
        }
    }
}

 

플로이드로 푸는 방법은 다음과 같다.

• 특정 정점에서 다른 모든 정점으로 이동할 수 있는지 확인한다.
• 이때 플로이드를 사용하여, i에서 j로 이동할 때 k를 거쳐서 이동할 수 있는지 확인하여 배열 값을 갱신한다.
• 이때 모든 정점이 순차적으로 k가 된다. 즉, k를 거쳐서 이동할 수 있는지 확인하고 모든 정점을 k로 치환하여 탐색했는데도 여전히 i에서 j로 이동할 수 없다면, 이동할 수 없는 것이다. 
• 시간 복잡도는 3중 반복문으로 인해 O(N^3)이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 시간 복잡도: O(N^3)
public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n;
    static int[][] map;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[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 (map[i][k] == 1 && map[k][j] == 1) { // i -> k -> j 이동이 가능한지 확인
                        map[i][j] = 1;
                    }
                }
            }
        }

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