[프로그래머스] 네트워크 / 자바

문제         

프로그래머스

1 번째 시도   

• DFS 문제
• 인접행렬 탐색할 때 대각선 기준으로 위 아래 둘 중 하나만 봐도 된다.
  
  • 이거 구현하려니 머리가 터질 것 같았다 패스 ~
• 방문한 적이 없다면 그 노드를 기준으로 dfs 해주고 answer++ 해준다..
  • dfs는 연결되어 있는 모든 노드들을 탐색한다.
  • 중복탐색을 방지하기 위해 visted = true인 곳은 가지 않는다.

import java.util.*;

class Solution {
     
    
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];
        int answer =0;
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                answer++;
                dfs(i, visited, computers);
            }
        }
        return answer;
    }
    
    public void dfs(int node, boolean[] visited, int[][] computers) {

        visited[node] = true;
        
        for(int i =0; i < computers[0].length; i++) {
            if(!visited[i] && computers[node][i] == 1) {
                dfs(i, visited, computers);
            }
        }
    }
}