[BOJ] 11724. 연결 요소의 개수- 그래프/BFS (Java)

[BOJ] 11724. 연결 요소의 개수- 그래프/BFS (Java)

Problem

제출일 : 2020-02-16

문제 풀이 시간 : 15M

난이도 : ★

---

link : https://www.acmicpc.net/problem/15651

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

input

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

Output

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

Example

input

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

output

2

Solution & Inpression

문제에 설명이 자세하지 않아

연결요소라는 것을 찾아보고 이해한뒤 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 283,972 kb

실행시간 : 1,352 ms

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Silver3_11724_연결요소 {
    static int N, M, ans;
    static boolean[][] graph;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();
        graph = new boolean[N + 1][N + 1];
        visit = new boolean[N + 1];
        for (int i = 0; i < M; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            graph[s][e] = true;
            graph[e][s] = true;
        }
        ans = 0;
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                BFS(i);
                ans++;
            }
        }
        System.out.println(ans);
    }

    private static void BFS(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(x);
        visit[x] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = 1; i <= N; i++) {
                if (!visit[i] && graph[cur][i]) {
                    visit[i] = true;
                    q.offer(i);
                }
            }
        }

    }
}