.leetcode(547. Number of Provinces)

https://leetcode.com/problems/number-of-provinces/

 

1. 2022/04/10 시도

소요시간: 38분

class Solution {
    private int[] rootArray;
    private int[] rank;
    public int findCircleNum(int[][] isConnected) {
        rootArray = new int[isConnected.length];
        rank = new int[isConnected.length];
        
        //init
        for (int i=0; i<rootArray.length; i++) {
            rootArray[i] = i;
            rank[i] = 1;
        }

        for (int i=0; i<rootArray.length; i++) {
            for (int j=i+1; j<rootArray.length; j++) {
                if (isConnected[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        
        Set<Integer> provinces = new HashSet<>();
        for (int i=0; i<rootArray.length; i++) {
            provinces.add(find(i));
        }
        
        return provinces.size();
    }
    
    private int find(int index) {
        if (index == rootArray[index]) {
            return index;
        }
        
        return rootArray[index] = find(rootArray[index]);
    }
    
    private void union(int i, int j) {
        int rootX = find(i);
        int rootY = find(j);
        if (rank[rootX] > rank[rootY]) {
            rootArray[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            rootArray[rootX] = rootY;
        } else {
            rootArray[rootX] = rootY;
            rank[rootY] += 1;
        }
    }
}

풀이 접근 과정

그래프 풀이로 접근했다.

find, union을 정의하고 세팅을 초기화해준다.

isConnected가 허용될 때만 union을 시킨다.

마지막 set을 통해 unique한 root를 세면 된다.

기본적으로 for 루프가 2번 돌고 union메소드에서 find메소드를 사용하는데, 이 때 또 O(n)이 되어 최종 O(n^3)의 시간복잡도를 갖는다.

 

느낀점

• 그래프에 대해서 공부하면서 이번 풀이를 풀었는데 시간복잡도가 길지만 굉장히 재미있는 접근이다. 예전에 위키에 대한 설계를 하면서 이런 접근을 했었는데 그때는 parent개념만 두었는데 그래프처럼 root개념을 적용했다면 좀 더 효율적인 설계가 되었을지 궁금해졌다.
  • https://leetcode.com/explore/learn/card/graph/618/disjoint-set/3843/
• dfs로도 풀 수 있다. visited와 dfs조합으로 하면 O(n^2)의 시간복잡도로도 풀 수 있다.

//dfs
class Solution {
    public int findCircleNum(int[][] isConnected) {
        boolean[] visited = new boolean[isConnected.length];
        
        int counter = 0;
        for (int i=0; i< visited.length; i++) {
            if (visited[i] == false) {
                dfs(isConnected, visited, i);
                counter ++;
            }
        }
        
        return counter;
    }
    
    private void dfs(int[][] isConnected, boolean[] visited, int from) {
        for (int i=0; i<visited.length; i++) {
            if (isConnected[from][i] == 1 && visited[i] == false) {
                visited[i] = true; 
                dfs(isConnected, visited, i);
            }
        }
    }
}

• 솔루션을 참고하면, bfs로도 풀 수 있다. 내가 보기엔 isConnected가 2차원배열이기때문에 가능한 것으로 보인다. N차원이었으면 bfs로는 불가능하지 않았을까 한다.

class Solution {
    
    public int findCircleNum(int[][] isConnected) {
        boolean[] V = new boolean[isConnected.length];
        
        Queue<Integer> queue = new LinkedList<>();
        
        int counter = 0;
        for (int i=0; i<V.length; i++) {
            if (V[i] == false) {
                queue.offer(i);
                while(!queue.isEmpty()) {
                    int from = queue.remove();
                    for (int j=0; j<V.length; j++) {
                        if (isConnected[from][j] == 1 && V[j] == false) {
                            queue.offer(j);
                            V[j] = true;
                        }
                    }
                }
                counter++;
            }
        }
        
        return counter;
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형