26. LEVEL 3 - 네트워크 - BFS/DFS

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

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

 

 

- 네트워크 하나를 그래프 하나라고 생각하면 된다.

- computer 이차원 배열에 존재하는 그래프의 개수가 네트워크의 개수임

- BFS/DFS 탐색은 하나의 그래프를 탐색하는 것이므로, 탐색이 끝났다면 모든 node들이 방문이 되어야 함, 하지만 트리가 여러개인 경우, 하나의 그래프 탐색을 했다하더라도, 방문하지 않은 node들이 있을 수 있다. 

 

1. 재귀를 활용한 DFS

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        boolean[] visit = new boolean[computers.length];
        
        // dfs가 끝났는데 방문하지 않은 노드가 있다면 네트워크가 더 있음
        for (int i = 0; i < computers.length; i++) {
            if(!visit[i]){
            	answer++;   
                dfs(i, visit, computers);			    
            }			
		}
        return answer;
    }
    
    public void dfs(int node, boolean[] visit, int[][] computers) {
		visit[node] = true;
		
		for (int next = 0; next < computers.length; next++) {
			if(node != next && !visit[next] && computers[node][next] != 0) {
				dfs(next, visit, computers);
			}
		}
    }
}

 

2. 큐를 활용한 BFS 풀이

import java.util.*;

class Solution {
    public static int solution(int n, int[][] computers) {
        int answer = 0;               
        boolean[] visit = new boolean[computers.length];
    	Queue<Integer> queue = new LinkedList<Integer>();
                
        for (int i = 0; i < computers.length; i++) {
            if(!visit[i]){
            	answer++;
                bfs(i, visit, computers, queue);			    
            }
		}        
        return answer;
    }
    
    private static void bfs(int node, boolean[] visit, int[][] computers, Queue<Integer> queue) {
    	queue.offer(node);
    	
		while(!queue.isEmpty()) {
			int com = queue.poll();
			visit[com] = true;
			
			for (int next = 0; next < computers.length; next++) {
				if(com != next && !visit[next] && computers[com][next] != 0) {
					queue.offer(next);
				}
			}
		}
	}
}