깊이/너비 우선 탐색(DFS/BFS) : 네트워크 ( 프로그래머스 / java )

programmers.co.kr/learn/courses/30/lessons/43162

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

 

 

*해결 과정

해당 문제는 결론적으로 최적화된 풀이법은 union이라고 합니다. 하지만 저는 문제 유형처럼 DFS나 BFS를 활용하는 방법을 생각했습니다. 그렇게 BFS를 이용하기로 했습니다. 

 

내가 임의로 시작한 0번 노드와 연결되어있는 노드들을 BFS로 쭉 검사하면 됩니다. BFS 함수 한번으로 해결하는 것이 아니라 일단 검사 자체는 주어진 n개를 모두 하는게 핵심입니다. 그래서 visited=false이면 방문한 적이 없기 때문에 이어진 노드들을 찾찾습니다. 이 순간 answer는 +1이 되고 근처에 있는 노드들은 다시 BFS queue에 추가됨가 동시에 visited=true로 변합니다. visited=true이면 이미 방문했으므로 그냥 지나치면 됩니다.

 

import java.util.*;
class Solution {
    
    int answer=0;
    
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];
        BFS(n,computers,visited);
        return answer;
    }
    
    public void BFS(int n, int[][] computers, boolean[] visited){
        Queue<Integer> queue = new LinkedList<>();
        for(int k=0;k<n;k++){
            if(visited[k]==false){
                queue.add(k);
                answer++;
            }
            
            while(!queue.isEmpty()){
                int from = queue.poll();
                for(int j=0;j<n;j++){
                    if(computers[from][j]==1 && visited[j]==false){
                        visited[j]=true;
                        queue.add(j);
                    }
                }
            }
        }
    }
}