[Python] 11724 연결 요쇼 개수

👉 11724 연결 요소 개수

[정답 코드]

import sys
sys.setrecursionlimit(10**6)

def dfs(graph, visited, n):
    visited[n] = 1
    for i in graph[n]:
        if visited[i] != 1:
            visited[i] = 1
            dfs(graph, visited, i)

n, m = map(int, sys.stdin.readline().split())
graph = {}
for i in range(n):
    graph[i + 1] = []
visited = [0] * (len(graph) + 1)
for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

visited[0] = 1
cnt = 0
while 0 in visited:
    node = 0
    for i in range(len(visited)):
        if visited[i] == 0:
            node = i
            break
    if node != 0:
        dfs(graph, visited, node)
        cnt += 1
print(cnt)

[풀이]

• 그래프를 구현하는 방법에는 인접 행렬(Adjacency matrix), 인접 리스트(Adjacency List)가 있는데 시간, 공간 복잡도를 고려해 인접 리스트로 구현하였다.
  - main에서 while문과 내부의 for문을 종합하면 O(N^2)의 시간복잡도가 나오지만, 정점의 개수 1 <= N <= 1000이라는 조건 때문에 그냥 진행했다. (python3 제출로는 1000000까지는 거뜬히 하더라..)
• dfs로 연결 요소를 하나씩 찾을때마다 cnt +=1 해주었다.

[오류 해결]
런타임에러(Recursion Error)
파이썬의 경우 recursionlimit이 1000이기 때문에 sys.setrecursionlimit(10**6)으로 해결해줄 수 있으나, 그 이상으로 recursion이 초과되는 경우 segmentation fault가 뜬다.

dfs보단 bfs, dp의 경우 재귀 대신 반복문 사용으로 해결할 수 있다. (링크 참조)

[적용 자료구조 및 알고리즘]

• Graph
• DFS, BFS