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

bfs 문제입니다.

 

노드 n이 자연수로, 간선이 2차원 배열 형태로 주어집니다.

그래프에 주어진 조건을 입력하고, 노드의 개수만큼 탐색을 하면 끝나는 문제입니다.

단, 탐색을 하면서 방문한 노드는 다시 방문하지 않게 해야 합니다.

 

[구현 코드]

import java.util.*;

class Solution {
    private static List<List<Integer>> graph;
    private static boolean[] visited;

    public static int solution(int n, int[][] computers) {
        int answer = 0;

        graph = new ArrayList<>();
        for(int i=0; i<n+1; i++) graph.add(new ArrayList<>());

        for (int i = 0; i < computers.length; i++) {
            for (int j = 0; j < computers[i].length; j++) {
                if(i == j) continue;

                if(computers[i][j] == 1){
                    graph.get(i+1).add(j+1);
                    graph.get(j+1).add(i+1);
                }
            }
        }

        visited = new boolean[n+1];
        for(int i=1; i<n+1; i++){
            if(!visited[i]) {
                bfs(i);
                answer++;
            }
        }

        return answer;
    }

    private static void bfs(int s) {
        Queue<Integer> qu = new LinkedList<>();
        qu.add(s);

        while (!qu.isEmpty()){
            int cn = qu.poll();

            if(visited[cn]) continue;
            visited[cn] = true;

            for(int i=0; i< graph.get(cn).size(); i++){
                qu.add(graph.get(cn).get(i));
            }
        }
    }
}