[LeetCode- Part. 3] 5. Province의 수 (+DFS)

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

Number of Provinces - LeetCode

 

2개

3개

1. 연결된 도시를 찾는다.

-> 직접연결과 간접연결

2. 초기값을 전달한 후, 초기값에서 연결된 모든 도시를 찾는다.

3. 연결된 모든 도시 찾기 종료 후, 다음 도시들은 모두 세면서 연결되어있는지 찾는다.

 

class Solution {
    static int answer;
    public int findCircleNum(int[][] isConnected) {
        //직접 연결과 간접 연결
        //[n][n]행렬에서 직접 연결 + 간접 연결된 모든 도시의 수
        int n=isConnected.length;
        // System.out.println("N"+n);
        boolean[] check = new boolean[n];
        answer=0;
        
        check[0]=true;
        answer++;
        DFS(isConnected, isConnected[0], 0, n, check);
        
        for(int i=1;i<n;i++){
            if(!check[i]){
                // System.out.println("돈다");
                answer++;
                DFS(isConnected, isConnected[i], i, n, check);
            }
        }

        // System.out.println(answer);
        return answer;
    }
    private void DFS(int[][] isConnected,int [] node, int i, int n, boolean[] check){
        for(int j=0; j<n;j++){
            if(!check[j] && node[j]==1) {
                //System.out.println("이번 : "+j);
                check[j]=true;
                // for(boolean x : check) System.out.print(x+" ");
                // System.out.println();
                DFS(isConnected, isConnected[j], j, n, check);
            }
        }
    }
}

 

 

+) 세련된 코드

class Solution {
    int n=0;
    
    public int findCircleNum(int[][] isConnected) {
        //1. ds
        n=isConnected.length;
        
        //방문 확인 배열
        //: 연결되어있지 않으면 1 연결되어있으면 0
        int[] visited = new int[n]; //[0,0,0];
        int count=0;
        
        //2. loop
        for(int i=0; i<n;i++){
            //방문하지 않았을 때
            if(visited[i]==0){
                DFS(isConnected, visited, i);
                count++;
            }
        }
        
        return count;
    }
    private void DFS(int[][] isConnected, int[] visited, int i){
        //깊이 우선 탐색 : n개만큼 돌면서 연결되어있는 모든 도시를 체크한다.
        for(int j=0; j<n;j++){
            //연결되어있고, 방문하지 않았을 때
            if(isConnected[i][j]==1 && visited[j]==0){
                visited[j]=1;
                DFS(isConnected, visited, j);
            }
        }
    }
}