Geeks For Geeks : Transitive closure of a Graph (Java)

문제 링크

The problem link : Geeks For Geeks - Transitive closure of a Graph(클릭)

문제 요약

1. N*N 배열 graph가 주어집니다. 이 배열은 방향이 있는 그래프를 뜻합니다.
2. graph[i][j]가 의미하는 것은, i 정점에서 j 정점까지 연결되어있는 (= 방향이있는) 간선이 있음을 뜻합니다.
3. 정점 i에서 j까지 (다른 정점을 거쳐서라도) 도달할 수 있는지를 가리키는 그래프를 출력하세요.

핵심 요약

문제 조건을 보면 예상 시간복잡도와 공간복잡도를 이렇게 언급했다.

Expected Time Complexity: O(N^3) // 시간복잡도 
Expected Auxiliary Space: O(N^2) // 공간복잡도

시간 복잡도를 보면 힌트가 나오는데, 이 문제는 플로이드 와샬 알고리즘(클릭)으로 접근하면 쉽게 해결할 수 있다.

문제 풀이

class Solution{
    static ArrayList<ArrayList<Integer>> transitiveClosure(int N, int graph[][])
    {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(N);


        int reach[][] = new int[N][N];

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

        for(int k=0; k<N; k++) { 
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    reach[i][j] = (reach[i][j]!=0) || ((reach[i][k]!=0) && (reach[k][j]!=0))?1:0;
                }
            }
        }

        for(int i=0; i<N; i++){
            res.add(new ArrayList<Integer>(N)); 
            for(int j=0; j<N; j++) { 
                if(i==j) res.get(i).add(1);
                else res.get(i).add(reach[i][j]);
            }
        }

        return res;
    }
}

플로이드 와샬 알고리즘을 이해하면 어렵지 않은 문제니 해설은 생략한다.