[Java] Lv.3 네트워크

문제

 

프로그래머스

 

문제 풀이

DFS를 활용하여 문제를 풀이했다. 컴퓨터 수 만큼 리스트를 만든다.(해당 컴퓨터와 연결된 다른 컴퓨터를 기록할 리스트)

방문한 적 없는 컴퓨터를 기준으로 DFS를 실행하여 방문한 적 없는 연결된 다른 컴퓨터를 계속 확인한다.

자바 코드

import java.util.*;

class Solution {
    private boolean[] visited;
    private List<List<Integer>> list;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        list = new ArrayList<>();
        
        // 컴퓨터 수 만큼 반복
        for(int i = 0; i < n; 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);
                }
            }
        }
        
        // 0번부터 네트워크 확인
        for(int i = 0; i < n; i++){
            // 방문한 적 없는 경우만 실행
            if(!visited[i]){
                // 현 컴퓨터를 방문처리
                visited[i] = true;
                // 연결 컴퓨터 확인
                dfs(i);
                // 정답 + 1
                answer++;
            }
        }
        
        return answer;
    }
    
    public void dfs(int i){
        // 컴퓨터에 연결된 다른 컴퓨터 확인
        for(int value : list.get(i)){
            // 방문 안 된 경우에 방문 처리하고 똑같이 연결 네트워크 확인
            if(!visited[value]){
                visited[value] = true;
                dfs(value);
            }
        }
    }
}