[JAVA] DFS/BFS "네트워크"

아래의 내용은 DFS로 구현하였다.

 

이 문제는 DFS로 푸는 문제인것을 확인했고, boolean visited[] 배열을 이용하여 방문한 노드를 체크하는 방식인 것도 알았다.

 

고민은,

한 뭉텅이가 연결되고, 카운트++;

한 뭉텅이가 연결되고, 카운트++;

 

위처럼 코드를 작동하게 하려면 어떻게 재귀함수를 작성하느냐였다.

 

결론은,

"main 메소드에서" 방문하지않은 노드들만 호출하는 동시에 카운트++;을 하면 된다.

 

그러면 메인 메소드에서,

한 뭉텅이당 하나의 노드만 호출되고, 나머지 노드들은 재귀로써 방문처리된다.

 

class Solution {
    void dfs(int i, boolean[] check, int[][] computers){
        check[i] = true;

        for(int j=0; j<computers.length; j++){
        //아래 세가지 조건에 해당하지 않는 경우에만 재귀.
        //1.현재위치(i=j)값x  2.연결되지않은노드  3.이미 방문한곳
            if(i != j && computers[i][j] ==1 && check[j] == false){
                dfs(j, check,computers);//업데이트
            }
        }
    }

    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] check = new boolean[n];
        for(int i =0; i<n; i++) {
            if (!check[i]){
                dfs(i, check, computers);
                answer++;
            }
        }
        return answer;
    }
}

1. 현재위치 i=j인경우

2. 연결되지 않은 노드

3. 이미 방문했던 노드

 

위 세가지 경우에는 노드를 방문하지않는다(dfs를 재귀호출하지않는다)