[Programmers] 네트워크

난이도 : Level 3

문제링크

• 컴퓨터 갯수와 각 컴퓨터의 연결 정보에 대한 2차원 정수형 배열이 주어진다
• 컴퓨터의 연결 정보에 대한 배열
  • i번 컴퓨터와 j번 컴퓨터의 연결상태를 나타냄
  • computers[i][j] == 1
• 네트워크 갯수를 구하라

 

해설

• 네트워크 전체를 탐색하기 위해 dfs 탐색을 시도합니다. (연결된 네트워크의 모든 노드들을 방문할 수 있습니다)
• dfs 탐색 대상 컴퓨터
  • 연결된 또 다른 컴퓨터가 존재함
  • (네트워크 탐색을 통해) 방문하지 않은 컴퓨터
• 혼자 있는 컴퓨터도 네트워크 이므로 네트워크 수에 더해줍니다
  • (네트워크 탐색 시에) 방문하지 않은 컴퓨터 입니다.

class Solution {    
    boolean[] visited;
    public int solution(int n, int[][] computers) {
        int answer = 0, r = computers.length, c = computers[0].length;
        visited = new boolean[n];
        
        for (int i = 0; i < r; i++) {            
            for (int j = 0; j < c; j++) {
                if (i == j) {                    
                    continue;   
                }
                
                if (computers[i][j] == 1 && !visited[j]) {                    
                    dfs(i, j, computers);
                    answer++;
                }
            }        
        }    
                
        for (boolean b : visited) {
            if (!b) {
                answer++;
            }
        }
                        
        return answer;                
    }
    
    private void dfs(int i, int j, int[][] computers) {
        visited[i] = true;
        visited[j] = true;
        
        for (int k = 0; k < computers[0].length; k++) {
            if (computers[j][k] == 1 && !visited[k]) {
                dfs(j, k, computers);
            }
        }
    }
}