[JAVA] 백준 (실버2) 11724번 연결 요소의 개수

링크

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

---

문제 설명

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

---

입력 예제

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

---

출력 예제

2

---

정답 코드

예제의 연결 성분을 구하면
[1, 2, 5] 와 [3, 4, 6]
총 2개의 그래프가 나온다.

모든 정점에 대하여 dfs를 진행하면서
모든 정점을 방문할 때까지 카운트한다.

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

public class Main {

    static HashMap<Integer, List<Integer>> adjList;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        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());   //간선의 수
        visit = new boolean[N + 1];
        int count = 0;
		//인접 리스트 생성
        adjList = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            adjList.put(i, new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }
		//정점을 반복하면서 dfs를 진행한다.
        for (Integer i : adjList.keySet()) {
        	//방문한 정점은 생략
            if (visit[i]) {
                continue;
            }
            dfs(i);
            count++;
        }

        System.out.println(count);
    }
	//dfs 메서드
    private static void dfs(int node) {
        visit[node] = true;

        for (Integer i : adjList.get(node)) {
            if (!visit[i]) {
                dfs(i);
            }
        }
    }
}

---

정리

dfs메서드는 DFS와 BFS 문제에서 사용한 dfs를 활용하였다.
처음에는 모든 정점에 대하여 연결 성분을 구하고 정렬하여 Set 컬렉션을 이용하였다.

Set<List<Integer>> graphs = new HashSet<>();

for (Integer i : adjList.keySet()) {
	graph = new ArrayList<>();	//연결 성분
	visit = new boolean[N + 1];
	dfs(i);
	Collections.sort(graph);
	graphs.add(graph);
}
        
System.out.println(graphs.size());

말그대로 연결 성분의 개수를 구하였는데 매 그래프마다 정렬을 해야되고
모든 정점에 대하여 진행해야했기 때문에 시간초과가 났었다.
정점이 최대 개수가 1,000개이고 이때 간선의 개수는 499,500개기 때문에
매번 정렬하려면 약 5억번의 연산을 해야한다.