[프로그래머스]Lv3. 네트워크

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

프로그래머스

 

커넥티드 컴포넌트

 

1. 연결되어 있는 노드들을 2차원 List에 담는다.

2. 1번노드부터, 연결된 노드들을 탐방하면서 방문처리를 해준다.

3. dfs()가 한번 끝난경우 == 한 네트워크를 의미하므로, 방문되지 않은 다음 노드(네트워크)를 dfs() 돌려준다.

 

풀이 코드

import java.util.*;

class Solution {
    
    public int[] visited;
    public List<List<Integer>> list;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        list = new ArrayList<>();
        
        visited = new int[n];
        
        for(int i = 0; i < computers.length; i++){
            list.add(new ArrayList<>());
            for(int j = 0; j < computers[i].length; j++){
                if(computers[i][j] == 1 && i!=j){
                    list.get(i).add(j);
                }
            }
        }
        
        
        for(int i = 0; i < n; i++){
            if(visited[i] == 0) {
                visited[i] = 1; // 자기 자신 방문 처리
                dfs(i);
                answer++;
            }
        }
        
        return answer;
    }
    
    public void dfs(int next) {
        for(int value: list.get(next)) {
            if(visited[value] == 0){
                visited[value] = 1;
                dfs(value);
            }
        }
    }
}

 

실행 결과