프로그래머스 dfs bfs 네트워크 자바

문제링크

풀이

return 값이 2일때

return 값이 1일때

문제를 보고 바로 이해하지 못했는데 엣지의 개수를 세는 것이 아니라 독립적으로 존재하는 네트워크의 개수를 새는 문제다.

bfs 큐를 이용해서만 풀어보다가 dfs 재귀를 이용해서 풀어보고 싶었는데, 직감적으로 dfs가 유리해 보인다. 사실 근거는 없다. 아무튼 고려해야할 사항은 dfs 도는 과정은 똑같지만 단순히 탐색을 하고 끝이 아니라 연결되지 않은 노드를 모두 탐색해야하고, 각 탐색은 count 되어야 독립적인 네트워크를 새 수 있다.

package argo.dfsAndBfs;
import java.util.*;
/*https://programmers.co.kr/learn/courses/30/lessons/43162?language=java*/
public class Network {
    static boolean[] visit;
    static int count;
    static int[][] map;
    public int solution(int n, int[][] computers) {
        visit = new boolean[n];
        map = computers;
        count = 0;
        for(int i=0;i<map.length;i++){
            if(!visit[i]){
            bfs(i);
            count++;
                }
        }
        return count;
    }
    static void bfs(int n){
        if(visit[n]) return;
        visit[n]= true;
        for(int i = 0; i< map.length;i++){
            if(!visit[i]&&map[n][i]==1&&n!=i){
                bfs(i);
            }
        }
        
        }
    }