[프로그래머스] 프로그래머스 Level3 네트워크 Java

문제

https://programmers.co.kr/learn/courses/30/lessons/43162

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

풀이

DFS로 해결할 수 있었다.

visited 배열을 만들어서 노드의 방문 여부를 체크할 수 있도록 해주었고, 이후에는 방문하지 않은 노드들에 대해서 깊이 우선 탐색을 시켜주어서 또 다른 연결된 노드들을 쭉 탐색시켜주었다.

이후 깊이 우선 탐색이 끝나면 연결 요소(네트워크)가 하나 만들어지는 것이므로 answer를 1 증가시켜주었고, 이러한 방법으로 모든 방문하지 않은 노드들에 대해 탐색을 진행시켜주면 네트워크의 개수 즉 정답을 얻을 수 있다.

코드

class Solution {

    boolean[] visited = new boolean[201];

    public int solution(int n, int[][] computers) {

        int answer = 0;

        for(int i = 0; i < computers.length; i++) {
            if(!visited[i]) {
                answer++;
                DFS(i, computers, computers.length);
            }
        }

        return answer;
    }

    void DFS(int n, int[][] computers, int size) {

        visited[n] = true;

        for(int i = 0; i < size; i++) {
            if(!visited[i] && computers[n][i] == 1) {
                DFS(i, computers, size);
            }
        }
    }
}