[JAVA] 프로그래머스 : 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162
처음에는 네트워크 분석 문제이기 때문에 bfs를 사용하려고 했다. 하지만, 이 문제는 모든 요소를 탐색하는 것이 목적이고, 그나마 구현이 간편한 dfs를 사용하기로 하였다.

우선, 문제에서 주어진 computers 배열을 보면 다음과 같다.

즉, computers[0][0]은 자기 자신을 의미하고, computers[0][1] = 1은 0번 컴퓨터에서 1번 컴퓨터로 연결된 선이 있다는 것을 의미한다.

이것을 이용해서 문제를 풀면 된다. 우선, main에서 각 컴퓨터를 방문했는지 아닌지를 판단하여 dfs 함수를 호출한다. 이후 dfs 함수에서는 그 컴퓨터에 연결된 선들을 모두 탐색하여 dfs함수를 수행하면 된다.

import java.util.*;

class Solution {
    private static boolean[] visited; //각 컴퓨터를 방문했는지 아닌지를 판단
    private static int[][] computer;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n]; //방문 여부를 저장할 배열
        computer = computers; //컴퓨터를 저장할 배열
        for(int i=0;i<n;i++){ //컴퓨터의 개수만큼 반복
            if(!visited[i]){ //방문하지 않은 컴퓨터라면
                dfs(i);
                answer++;
            }
        }
        return answer;
    }
    private static void dfs(int now){
        visited[now] = true;
        for(int i=0;i<computer[now].length;i++){
            if(computer[now][i] == 1 && !visited[i]){ //컴퓨터에 회선이 있고 방문하지 않은 회선이라면
                dfs(i);                
            }
        }
    }
}