[백준 11724번] 연결 요소의 개수 - Python, DFS/BFS

문제

11724번: 연결 요소의 개수

정점(N)과 간선(M)의 개수가 주어질 때 연결 요소의 개수를 구하라.
(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
간선 u, v  (1 ≤ u, v ≤ N, u ≠ v)

 

대표적인 DFS/BFS 문제이다.

시간 제한 3초, 메모리 제한 512 MB에 주의해야 한다.

---

풀이

✏️ DFS

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

n, m = map(int, input().split())

graph = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


def recur(node):
    visited[node] = 1

    for nxt in graph[node]:
        if visited[nxt] == 1:
            continue
            
        recur(nxt)
        
cnt = 0

for i in range(1, len(visited)):
    if visited[i] == 0:
        recur(i)
        cnt += 1

print(cnt)

아이디어

1 [2, 5]

2 [1, 3, 5]

3 [2]

4 [7]

5 [1, 2, 6]

6 [5]

7 [4]

 

다음과 같이 그래프를 나타내고 방문체크를 하면 순회한다.

visited = [0, 0, 0, 0, 0, 0, 0, 0] -> visited = [0, 1, 1, 1, 1, 1, 1, 1] (정점이 1부터 시작)

 

재귀는 만들었는데 끊기고 방문하지 않은 부분에서 다시 시작하는 것에서 막혔다가 아직 방문하지 않은 visited(0)이 있으면 다시 재귀를 도는 방법으로 풀었다.

 

처음 제출시 런타임 에러 (RecursionError)가 나서 백준 질문 게시판을 참고해 재귀 깊이 제한을 늘려줬다.

sys.setrecursionlimit(10000)

 

실제 파이썬 재귀 깊이 제한은 1000으로 필요시 위와 같이 늘려주면 된다. 실제로 확인하는 방법은 아래와 같다.

 

limit = sys.getrecursionlimit()
limit2 = sys.getrecursionlimit()

print(limit, limit2) # 1000, 10000

 

---

✏️ BFS

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] for i in range(N+1)]
visited = [0 for i in range(N+1)]

for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

queue = deque()

def bfs(i):
    queue.append(i)
    while queue:
        node = queue.popleft() # 선입선출
        visited[node] = 1

        for nxt in graph[node]:
            if visited[nxt] == 1:
                continue
                
            queue.append(nxt)
            visited[nxt] = 1

cnt = 0

for i in range(1, N+1):
    if visited[i] == 0:
        bfs(i)
        cnt += 1

print(cnt)

 

아이디어

• BFS도 DFS처럼 graph와 visited를 만들어 주고 deque를 이용해 popleft로 들어간 순서대로 빼주면서 queue가 있는 동안 순회를 돌면 된다.

BFS는 시간 초과, 메모리 초과 에러가 났는데 node를 방문할 때와 다음 node를 큐에 추가할 때 모두 방문 처리를 해줘야 중복을 피할 수 있었다.

visited[node] = 1

visited[nxt] = 1

 

 

시간 복잡도 - O(N + M)

DFS, BFS 모두 그래프를 한 번씩 전체 탐색하므로 시간 복잡도는 O(N + M) 노드 + 간선의 수이다.

 

공간 복잡도 - O(N)

BFS는 deque를 사용해 현재 노드에 방문할 노드들을 저장하고, 최악의 경우 모든 노드를 queue에 넣을 수 있으므로 공간 복잡도는 O(N)이다.

DFS는 재귀 호출을 사용하며, 최악의 경우 호출 스택에 모든 노드가 쌓일 수 있으므로 공간 복잡도는 O(N)이다.

 

 

---

 

DFS, BFS 개념이 없다면 먼저 공부하길 추천한다. 나도 계속 복습 중인데 진짜 자기가 그려보면서 이해해야 풀 수 있다.