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

• 문제 링크 : 네트워크

코딩테스트 연습 - 네트워크

 

정답(Solution) - 20220209 다시 풀이

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;

        boolean[] v = new boolean[n];

        for(int i=0; i<n; i++){
            if(!v[i]){
                dfs(n, v, 0, i, computers);
                answer++;
            }
        }

        return answer;
    }

    private void dfs(int n, boolean[] v, int depth, int idx, int[][] computers){
        v[idx] = true;

        if(n-1 == depth){
            return;
        }

        for(int i=0; i<n; i++){
            if(!v[i] && i != idx && computers[idx][i] == 1){
                dfs(n, v, depth + 1, i, computers);
            }
        }
    }
}

 

분석

행렬은 노드의 연결 관계를 나타낸다.

 

해당 문제는 dfs를 반복하는 것으로 root가 여러개 있다고 생각하면 된다.

 

for문으로 돌면서 각 root에서 dfs를 해주고 각 root들을 방문했는지 체크하는 int[] visted가 있다.

 

visited에 이미 1로 되어있는 것은 다른 root에서 해당 노드를 방문한 것이기 때문에 네트워크에 속한다.

 

그래서 visited에 없는 dfs를 수행하여햐 네트워크수를 카운트 할 수 있다.

 

이전 정답

class Solution {
    public int solution(int n, int[][] computers) {
        int[] visited = new int[n];

        int answer = 0;

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


        return answer;
    }

    private void dfs(int[][] computers, int nodeNum, int[] visited){
        visited[nodeNum] = 1;

        if(nodeNum == computers.length){
            return;
        }else{
            for(int nextNum = 0; nextNum < computers.length; nextNum++){
                if(nodeNum != nextNum 
                   && computers[nodeNum][nextNum] == 1
                   && visited[nextNum] != 1){
                    dfs(computers, nextNum, visited);
                }

            }
        }
    }
}

 

Stack 풀이 추가 20220320

import java.util.*;

class Solution {
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] v = new boolean[n];
        
        for(int i=0; i<n; i++){
            if(!v[i]){
                Stack<Integer> stk = new Stack<>();

                stk.push(i);

                while(!stk.isEmpty()){

                    Integer num = stk.pop();
                    v[num] = true;

                    for(int j=0; j<n; j++){
                        if(i == j) continue;
                        if(v[j]) continue;
                        if(computers[num][j] == 1){
                            stk.push(j);
                        }
                    }
                }
                
                answer++;
            }
        }
        
        return answer;
    }
}