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

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

프로그래머스

풀이 방법

완전 탐색 + 그래프 탐색 방법으로 방문하지 않은 노드일 때 그 점부터 그래프 탐색을 하며 연결된 지점을 같은 네트워크로 묶고 answer를 +1 해주고 다시 완전 탐색으로 방문하지 않은 노드를 찾아 그래프 탐색을 하는 방식으로 해결했다.

 

import java.io.*;
import java.util.*;
class Solution {
    static int N;
    static int[] visited;
    static int[][] graph;        
    
    public void bfs(int now) {
        Queue<Integer> q = new LinkedList<>();
        q.add(now);
        while (!q.isEmpty()) {
            int p = q.poll();
            for (int i = 0;i < N;i++) {
                if (p == i) continue;
                if (visited[i] == 1) continue;
                if (graph[p][i] == 0) continue;
                q.add(i);
                visited[i] = 1;
            }            
        }
        return;
        
    }
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new int[n];
        graph = new int[n][n];
        graph = computers;
        N = n;
        for (int i = 0;i < N;i++) {            
            if(visited[i] == 0) {
                answer += 1;
                visited[i] = 1;
                bfs(i);                                    
            }
        }
        return answer;
    }
}