백준 11724번: 연결 요소의 개수

풀이

-몇 개의 연결요소(component)가 있는지 구하는 문제
-무향 그래프의 component: 하위 그래프이고 노드가 간선과 연결돼 있으면서, 다른 하위 그래프와 간선으로 연결되어 있지 않은 것.

출처
https://en.wikipedia.org/wiki/Component_(graph_theory)

-인접점의 정보를 설정 뒤, 노드를 넣으면 연결된 노드들을 방문 처리하는 bfs메소드를 만든다. 방문하지 않은 노드를 bfs에 넣으면 하나의 component가 완성되면서 component안의 노드들은 방문 처리된다.

public class Problem11724 {
    static int nodeNum, edgeNum, answer = 0;
    static boolean[] visited;
    static int[][] connect;

    //startNode와 연결된 연결요소를 탐색
    public static void bfs(int startNode){

        Queue<Integer> queue = new LinkedList<Integer>();

        queue.add(startNode);
        visited[startNode] = true;


        while(!queue.isEmpty()){
            int currNode = queue.poll();
            for(int i = 0; i < connect.length; i++){
                //간선이 있고 방문하지 않은 경우 큐에 추가
                if(connect[currNode][i]==1 && !visited[i]){
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
        //한개의 연결 요소를 탐색 후 answer 증가
        answer++;

    }



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");

        //노드 수, 간선 수, 방문 목록, 간선 배열 설정
        nodeNum = Integer.parseInt(st.nextToken());
        edgeNum = Integer.parseInt(st.nextToken());
        visited = new boolean[nodeNum+1];
        connect = new int[nodeNum+1][nodeNum+1];

        for(int i = 0; i < edgeNum; i++){
            String edgeInfo = br.readLine();
            StringTokenizer edgeSt = new StringTokenizer(edgeInfo, " ");
            int firNode = Integer.parseInt(edgeSt.nextToken());
            int secNode = Integer.parseInt(edgeSt.nextToken());

            connect[firNode][secNode] = 1;
            connect[secNode][firNode] = 1;
        }

        //맨 앞 노드부터 bfs메소드에 넣는다. 배열의 0번째 값은 없는 값이기 때문에 넣지 않는다.
        for(int i = 1; i < visited.length; i++){
            if(!visited[i]){
                bfs(i);
            }
        }

        System.out.println(answer);


    }
}

개선할 점

BFS메소드의 시간복잡도는 노드 하나 당 다른 노드의 연결 여부를 모두 조회하기 때문에 O(N^2)이다.
인접점의 형태를 이차원 배열이 아닌 해시맵의 형태로 구현했다면 노드 하나당 연결된 간선만 조회하기 때문에 O(N+E)가 될 것이다.