[Programmers] 네트워크 - Java

 

Level 3

코딩테스트 연습 - 네트워크

 

문제 풀이

DFS 문제

자기자신을 방문처리하고,

연결된 노드이면서 방문하지 않은 노드의 인덱스를 다시 재귀함수의 매개변수로 주어 모든 연결된 노드들을 dfs로 방문한다. 

재귀가 끝날 때마다 count(내 코드에선 answer변수)를 올려 네트워크의 개수를 센다.

 

코드

class Solution {
    public void dfs(int index, int[] visited, int[][] computers) {
        visited[index] = 1;

        for (int i=0; i<computers.length; i++) {
            if (visited[i] == 0 && computers[index][i] == 1 && index != i) {
                dfs(i, visited, computers);
            }
        }
    }

    public int solution(int n, int[][] computers) {
        int[] visited = new int[n];
        int answer = 0;

        for (int i=0; i<n; i++) {
            if (visited[i] == 0) {
                dfs(i, visited, computers);
                answer += 1;
            }
        }
        return answer;
    }
}