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

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

프로그래머스

 

이 문제를 왜 혼자 못풀었을까 .... 문제 푼 방법 설명해보겠다..

 

일단 visited를 하나 선언함으로써 연결된 컴퓨터 사이의 관게를 파악할 수 있도록 한다. 이후로 visited를 차례로 돌면서 네트워크가 다른 네트워크랑 연결되어있는지 확인하고, 만약 visited가 false면 일단 네트워크의 개수를 하나 증가시킨다. (연결되어있다면 dfs 내에서 visited에 해당하는 값을 true로 바꿀 거니까 본인에 대해서는 개수 추가) 그리고 나서 dfs에 들어가게 되는데 현재 방문한 네트워크에 대해서 visited를 true로 변경하고 0부터 computers의 원소 개수만큼 돌면서 visited의 값이 false면서 computers의 x, i 번째 원소가 1인 경우는 다시 dfs를 탐색한다. 

이렇게 해줘야 연결된 값에 대해서는 dfs 내에서 visited를 true로 바꿔주고, 연결되지 않은 값은 다시 dfs 밖으로 나가서 main 함수의 for문 내부에서 다시 dfs로 탐색하게 된다.

 

lv3 치고는 어렵지 않은 문제였는데 스스로 못푼 게 아쉽다. 다시 풀어봐야지 ...^^

 

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

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