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

🔗 문제 링크

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

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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-5), (3-4-6)으로 총 2개이다.

---

💻 나의 코드

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

def dfs(i):
    if visited[i]:
        return

    visited[i] = True
    for j in adj[i]:
        dfs(j)

n, m = map(int, input().split())
adj = dict()
for i in range(1, n+1):
    adj[i] = list()
    
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
    adj[u].sort()
    adj[v].sort()

answer = 0
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        dfs(i)
        answer += 1

print(answer)

첫 번째 제출에서는 visited를 set으로 선언해 코드를 제출하였다. 맞았습니다!! 를 받긴 했지만, 메모리 사용량과 실행 시간을 보면 메모리 초과나 시간 초과를 받아도 이상하지 않을 수준이다.

 

두 번째 제출에서는 visited를 다시 list로 선언해 코드를 제출하였다. 메모리 사용량과 실행 시간이 조금 줄어들긴 했지만, 여전히 리소스 사용량이 많은 편이다.😵

 

🕓 시간 복잡도 개선

다음은 elq007님의 코드를 참고하여 다시 작성한 코드이다.

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

def dfs(i):
    visited[i] = True

    for j in range(1, n+1):
        if not visited[j] and adj[i][j]:
            dfs(j)

n, m = map(int, input().split())
adj = [[0 for _ in range(n+1)] for _ in range(n+1)]
    
for _ in range(m):
    u, v = map(int, input().split())
    adj[u][v] = 1
    adj[v][u] = 1

answer = 0
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        if not adj[i]:
            answer += 1
            visited[i]
        else:
            dfs(i)
            answer += 1

print(answer)

그래프를 표현하는 방식이 인접 리스트에서 인접 행렬로 바뀌었다. 메인 함수의 for문을 보면 visited[i]가 false라고 무조건 dfs를 수행하는 것이 아니라, adj[i]가 0일 때, 연결되지 않은 경우에는 바로 카운트를 1 늘려준다. 이러한 방식으로 시간 복잡도를 크게 개선할 수 있었던 것으로 보인다.🧐