문제 출처

코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 네트워크
https://school.programmers.co.kr/learn/courses/30/lessons/43162

문제 설명

(문제의 입출력 예시 사진은 너무 커서 생략)

접근 방법

BFS를 이용하여 네트워크를 다 탐색한다. 시작 노드 start를 큐에 삽입하고, 큐에서 poll하여 해당 값과 연결된 노드들을 큐에 삽입한다. 이 과정을 반복한다.
이 BFS를 네트워크 탐색 확인용 visited의 모든 요소가 true가 될 때까지 반복한다.

import java.util.*;


class Solution {
    
    static boolean visited[];
    static int answer;
    
    public void bfs(int[][] computers,int n, int start){
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;
        
        while(!q.isEmpty()){
            int point = q.poll();
            visited[point] = true;
            for(int i = 0; i<n; i++){
                if(visited[i]) continue;
                if(computers[point][i] == 1){
                    q.offer(i);
                }
            }
        } 
        answer++;
    }
    
    public int solution(int n, int[][] computers) {
        answer = 0;
        visited=new boolean[n];
        
        for(int i = 0; i<visited.length; i++){
            if(visited[i]) continue;
            bfs(computers,n,i);
        }
        return answer;
    }
}

Review
코드 동일

Review(DFS 문제 풀이)
DFS로 문제를 풀이할 때, visited의 start(시작 노드) 를 true로 변경하고, start와 연결 된 노드들에게 dfs를 실행시켜주면 된다.
마찬가지로 dfs를 실행시킬 때, visited를 확인하여 false인 경우만 실행시켜주면 answer의 값을 알 수 있다.

import java.util.*;

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

알게된 점

기존에 풀었던 문제인 전력망을 둘로 나누기 문제와 비슷한 양상을 가진다. 전에 풀었던 문제는 전체 네트워크가 트리 구조여서 모두 연결되어 있으나, 이 문제에서는 끊겨있는 네트워크가 여러가 존재한다. 그래서 따로 간선을 끊어줄 필요는 없고, visited가 모두 true가 되면 답을 알 수 있다.

[JAVA] 전력망을 둘로 나누기
https://velog.io/@ms000320/JAVA-%EC%A0%84%EB%A0%A5%EB%A7%9D%EC%9D%84-%EB%91%98%EB%A1%9C-%EB%82%98%EB%88%84%EA%B8%B0

Reivew
동일한 부분에서 약간은 해맸었다. 다른 사람들은 전부 dfs로 푼 것을 보니 나도 dfs로 한 번 풀어봐야겠다.

Review(DFS 문제 풀이)
dfs를 유츄하는데는 어렵지 않았지만, dfs의 종료 조건에 대해서 계속 생각했다. 종료조건에 대해서 설정하기 어려워 다른 사람들이 푼 것을 보니 종료조건이 따로 필요하지 않았다. 이는 dfs목적이 한 네트워크에 대한 탐색에만 있기 때문에 시작 노드와 연결된 노드들 모두를 true로 바꿔주면 되기 때문이다. 심지어는 depth도 필요없는데 네트워크의 길이는 정해져 있지 않기 때문이다.

문제푼 흔적

Review