[백준] 연결요소의 개수(11724) - Java

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

---

출력

첫째 줄에 연결 요소의 개수를 출력한다.

---

예제 입력 1 

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 

2

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

 

내가 푼 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static boolean[] visited;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N + 1][N + 1];
        visited = new boolean[N + 1];

        // arr 값 세팅
        for (int i = 0; i < M; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());

            arr[a][b] = 1;
            arr[b][a] = 1;
        }

        int cnt = 0;
        for (int i=1; i<=N; i++) {
            if (!visited[i]) {
                bfs(i, N, arr);
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    private static void bfs(int node, int N, int[][] arr) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(node);

        while (!queue.isEmpty()) {
            int currNode = queue.poll();

            for (int i=1; i<=N; i++) {
                if (arr[currNode][i] == 1 && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}

 

BFS(인접 행렬)로 처리하였다.

 

1. 인접 행렬로 처리할때 두 노드 사이에 간선이 있으면 1, 아니면 0으로만 표시해준다.

node 번호를 index와 맞추기 위해 N+1 칸으로 arr을 생성해준다. 

 

2. 해당 노드에 방문했었는지를 확인하기 위한 visited 배열도 생성해준다.

 

3. arr에 값을 세팅해줄때 입력받는 입력예제 1번에서 1번과 2번노드 사이에는 간선이 존재하므로 1로 입력해주는데 이때, 방향성이 없는 그래프라고 문제에 나와있다.

방향성이 없다는 말은 양방향이라는 말과 동일하므로 arr[1][2] = 1, arr[2][1] = 1 로 입력해준다.

 

4. visited[]가 false 이면 bfs() 메서드에서 처리해준다.

 

bfs방식은 queue를 이용하는 것이다.

queue에 시작 노드번호를 넣어주고, queue가 empty 될때까지 반복문을 돌리는데 queue에서 하나씩 poll() 해주고 그 값을 문제에 따라 필요한 방식으로 처리해주면 된다.