[ 백준 - 11724 ] 연결 요소의 개수 with 그래프

그래프 구현 방법

	인접 행렬	인접 리스트
공간 복잡도	O( V^2 )	O( V+E )
정점 u, v가 연결되어있는지 확인하는 시간 복잡도	O( 1 )	O( min(deg(u), deg(v) )
정점 v와 연결된 모든 정점을 확인하는 시간 복잡도	O(V)	O( deg(V) )
효율적인 상황	두 점의 연결여부를 자주 확인할 때 E가 V^2에 가까울 때	특정 정점에 연결된 모든 정점을 자주 확인할 때 E가 V^2보다 훨씬 작을 때

 

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

 

난이도 : S2

Link  : https://www.acmicpc.net/problem/11724

Tag : Graph

 

문제 탐색하기 

- 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하여라

시도 1 ( 성공 😲)

떠오른 문제 해결 방법

이번 문제에서는 연결리스트를 활용하여 Graph를 구현하였고, BFS를 통해 연결 요소의 개수를 구하였습니다.

 

 

시간복잡도⏰

하나의 시작점에서 같은 연결 요소에 속한 모든 노드를 탐색하며, 한 번만 탐색하게 됩니다.

즉, BFS 전체에서 O(n + m)만큼  탐색하게 됩니다.  (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)  이므로 시간 제한 3초안에 해결이 가능합니다.

구현 방법 

세부 구현 사항

1. 주어진 값을 입력받는다.

2. 시작점을 1부터 n까지 설정한다.

3. 방문하지 않았을 경우 count를 1로 증가시키고 bfs를 통해 같은 연결 요서의 점들을 모두 방문한다.

import java.io.IOException;
import java.util.*;
import java.io.*;

class Main {
    private static int count = 0;
    private static int[] visit;
    private static int n;
    private static int m;

    public static int bfs(List<List<Integer>> graph) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (visit[i] == 1) {
                continue;
            }
            count++;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(i);
            visit[i] = 1;
            while (!queue.isEmpty()) {
                List<Integer> points = graph.get(queue.poll());
                for (int p : points) {
                    if (visit[p] == 1) {
                        continue;
                    }
                    queue.add(p);
                    visit[p] = 1;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        List<List<Integer>> graph = new ArrayList<>();
        visit = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            graph.get(s).add(e);
            graph.get(e).add(s);
        }
        System.out.println(bfs(graph));
    }
}

 

마무리

자주 풀면서 그래프 자료구조에 익숙해지자!

다른 다익스크라, 플로이드 알고리즘들 카테고리 문제의 기초 체력이 된다.