[프로그래머스] (JAVA) Lv3 네트워크

문제

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

프로그래머스

설명

입출력

나의 풀이

설명

예시 1을 예로 들어서보면

computers는 노드들 사이의 관계를 그동안 보던 인접리스트가 아닌 인접행렬로 주어졌다. 

computers를 출력해 보면 아래와 같은데 

즉, 0번 네트워크는 0번, 1번과 연결되어 있고 1번 네트워크는 0번, 1번 네트워크와 연결되어 있고

2번 네트워크는 2번과 연결되어 있는 것이다. 

연결되어있는 네트워크를 확인하기 위해 dfs를 구현하여 모든 노드를 방문하는 코드를 작성했다. 

import java.util.*;

class Solution {
    static int count = 0;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        boolean[] visited = new boolean[n];
        System.out.println("처음 visited");
        System.out.println(Arrays.toString(visited));
        System.out.println();
        
        dfs(0,computers, visited);
        System.out.println();
        System.out.println("dfs 후 visited");
        System.out.println(Arrays.toString(visited));
       
        return answer;
    }
    
    public static void dfs(int start, int[][] computers, boolean[] visited) {
        visited[start] = true;
        
        System.out.println("current_node: " + start);
        int[] check = computers[start];
        for(int i=0; i < check.length; i++) {
            if(i == start) continue;
            if(!visited[i] && check[i] == 1) {
                
                dfs(i,computers, visited);
            }
        }
    }
}

위의 코드를 실행해 보면

solution메서드에서 dfs 한 번으로 탐색을 시도하면 노드가 끊긴 경우 나머지는 탐색하지 못하게 된다. 

끊긴 노드들 각각을 탐색하려면 solution메서드에서 반복문으로 각 노드를 확인하며 dfs를 실행시켜 주었다.

방문 여부를 체크하며 dfs실행하고 dfs가 실행된다면 연결되지 않은 네트워크를 탐색한다는 의미이기 때문에 answer에 1씩 더해주었다.

dfs 풀이

import java.util.*;

class Solution {
    static int count = 0;

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

        boolean[] visited = new boolean[n];

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

    public static void dfs(int start, int[][] computers, boolean[] visited) {
        visited[start] = true;
        int[] check = computers[start];
        
        for(int i=0; i < check.length; i++) {
            if(i == start) continue;
            if(!visited[i] && check[i] == 1) {
                dfs(i,computers, visited);
            }
        }
    }
}

bfs 풀이

import java.util.*;

class Solution {
    static int count = 0;

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

        boolean[] visited = new boolean[n];

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

    public static void bfs(int start, int[][] computers, boolean[] visited) {
        visited[start] = true;
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        
        while(!q.isEmpty()) {
            int now_node = q.poll();
            int[] check = computers[now_node];
            for(int i=0; i < check.length; i++) {
                if(i == start) continue;
                if(!visited[i] && check[i] == 1) {
                    visited[i] = true;
                    q.add(i);
                }
            }
        }
    }
}

dfs로 풀면서 든 생각은 어차피 모든 노드를 탐색하는 게 목표이고 모든 노드를 탐색하는 것은

dfs, bfs가 마찬가지라는 생각이 떠올라서 bfs 코드로도 작성해 보았다. 

dfs                                                                                                                            bfs

속도는 dfs가 더 빠르다.