문제

풀이

이해

정점의 개수와 해당 정점이 이루는 그래프의 인접행렬을 입력받는다. 그래프는 가중치가 없는 방향 그래프이다. 입력받은 그래프의 관계를 바탕으로 경로의 유무를 판단하면 된다.

방향 그래프인 점을 주의해야 하는데 A->B의 간선은 B->A를 의미하지 않는다.

접근

최초에는 DFS를 통해 모든 인접 경우에서 경로가 있는지를 판단하는 알고리즘을 생각해보았다.

(0,0) 부터 (N,N)까지 인접행렬의 정보를 바탕으로 DFS를 실시하여 만일 도달할 수 있는 정점 중에 열(column) 값이 있다면 true를 반환, 아니라면 false를 반환한다.

        for (int i = 0; i < N; i++) {   //경로의 유무를 판단
            for (int j = 0; j < N; j++) {
                if (DFS(i, j)) {
                    ans[i][j] = 1;
                }else{
                    ans[i][j] = 0;
                }
            }
        }
        public static boolean DFS(int start, int end) { //DFS
           for (int i = 0; i < N; i++) {
              if (graph[start][i] == 1) {
                  if (i == end) {
                      return true;
                  } else {
                      return DFS(i, end);
                  }
              }
           }
           return false;
       }
        

하지만 당연하게도 시간초과가 발생하였다. 그래프 탐색 문제에서는 이런 식으로 모든 경우에서 재귀적으로 탐색을 하면 시간초과가 발생할 수 밖에 없다. 따라서, 다른 방법에 대해서 생각해보았다.

경로가 있다는 말은 중간 노드를 거치든 거치지 않든 목적지로 가면 그만이라는 것을 의미한다. 그렇다면 1->4, 4->5라는 정보가 있을 때, 1->5인 것은 자명하다. 다르게 생각해보자. 1->4일때, 만일, 거쳐가는 중간노드가 4라면 1은 4와 연결된 어디든 지 갈 수 있다.

따라서, N -> M 일때, N행의 인접행렬 정보는 M행의 인접행렬과 OR 연산을 수행하면 된다!
(M이 가는 곳은 N 역시 갈 수 있으므로)

이를 반복처리하면 경로가 존재하는 행렬 정보를 얻을 수 있게된다. 물론, 반복할 때마다 경로의 유무가 누락될 수 있기 때문에 행렬정보가 변화가 없을 때 까지 반복하는 것이 좋다.

코드

시간초과 코드

package java_baekjoon;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class prob11403 {
    static Queue<Integer> que = new LinkedList<>();
    static int N;
    static int[][] graph;
    static int[][] ans;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        graph = new int[N][N];
        ans = new int[N][N];
        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < N; i++) {   //경로의 유무를 판단
            for (int j = 0; j < N; j++) {
                if (DFS(i, j)) {
                    ans[i][j] = 1;
                }else{
                    ans[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
        sc.close();
        return;
    }

    public static boolean DFS(int start, int end) { //DFS
        for (int i = 0; i < N; i++) {
            if (graph[start][i] == 1) {
                if (i == end) {
                    return true;
                } else {
                    return DFS(i, end);
                }
            }
        }
        return false;
    }
}

정답 코드

package java_baekjoon;

import java.util.Scanner;

public class prob11403_2 {
    static int N;
    static int[][] graph;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        graph = new int[N][N];

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                graph[i][j] = sc.nextInt();
            }
        }

        while(true){
            int cnt = 0;

            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(graph[i][j] == 1){
                        for(int k=0;k<N;k++){
                            if(graph[j][k] == 1 && graph[i][k] == 0){
                                cnt++;
                                graph[i][k] = 1;
                            }
                        }
                    }
                }
            }

            if(cnt == 0){
                break;
            }
        }

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

        sc.close();
        return;
    }
}

결과

중간 노드를 통한 경로 파악은 플로이드 워셜 알고리즘라고도 한다. (A->B, B->C 는 A->C)