백준 11724번 파이썬

문제 링크

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

11724번: 연결 요소의 개수

 

시간 제한 / 메모리 제한

3 초

512 MB

 

문제

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

 

입력

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

출력

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

예제 입력

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

예제 출력

2

문제 풀이를 위해 생각한 것

1. 무방향 그래프 = 양방향 그래프
2. "정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)"에서 'M <= N*(N-1)/2' 는 무슨 뜻일까?
   1. 본 문제의 그래프는 N개의 정점이 있는 무방향 그래프 즉 양방향 그래프이고, 중복되는 간선은 입력으로 주어지지 않는다.(두 정점 간 간선은 오직 하나이다.)
   2. 이때 정점 N이 본인을 제외한 모든 N-1개의 정점과 연결되어 있다면, 두 정점 간 간선은 하나만 존재하기에, 총 간선의 갯수는 N*(N-1)/2로 나타낼 수 있다.
   3. 즉 간선의 갯수 M이 N*(N-1)/2보다 작거나 같다는 것은 N개의 정점이 N-1개의 다른 모든 정점과 연결되어 있는 밀집 그래프 상태를 나타낸다.
3. 밀집그래프인 상황에서는 인접행렬과 인접리스트 중 조회의 시간복잡도가 O(1)인 인접행렬을 통해 그래프를 구현할 수 있다.

 

사용한 자료구조 / 알고리즘

배열(인접행렬) / DFS.

간선의 수가 매우 많은 밀집 그래프에서는 공간 복잡도는 인접행렬, 인접리스트 모두 비효율적이다. 그러나 적어도 인접행렬은 조회의 시간복잡도가 O(1)이기에 인접행렬을 사용했다.

 

인접행렬: 조회의 시간복잡도 O(1), 공간복잡도 항상 O(V^2)

인접리스트: 조회의 시간복잡도 O(N), 공간복잡도 최악의 경우 O(V^2). 하지만 배열과 달리 간선의 갯수만큼 공간 할당.

 

결국 모든 정점을 방문해야 하는 완전 탐색 문제이기에 DFS, BFS 모두 사용할 수 있지만, 평소 잘 쓰지 않았던 DFS를 연습하기 위해 DFS로 탐색했다.

 

풀이 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, M = map(int, input().split())
graph = [[[0] for _ in range(N)] for _ in range(N)]
chk = [False] * N
res = 0


def dfs(n):
    for i in range(len(graph[n])):
        if graph[n][i] == 1 and not chk[i]:
            chk[i] = True
            dfs(i)


for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u][v] = graph[v][u] = 1

for i in range(N):
    if not chk[i]:
        dfs(i)
        res += 1

print(res)

 

시간 복잡도 분석

O(N^2).

모든 서로 다른 정점이 연결돼있을 경우, N*(N-1)/2번 탐색하지만, 최대차항의 계수를 제외하면 O(N^2).

 

문제에서 중요한 부분

간선은 최대 몇개 있고, 어떤 자료구조를 활용해 그래프를 나타낼 것인가를 고민해봐야 함.