[DFS] 백준 #11724 연결 요소의 개수 구하기 - Python

📚 문제

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

11724번: 연결 요소의 개수

 

💡 접근법

문제에서 말하는 연결 요소란 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 말한다.

따라서 DFS를 수행한 횟수를 계산하면 된다.

DFS란?
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

💻 코드

1) 전체 코드

import sys
sys.setrecursionlimit(10000)

N, M = map(int, sys.stdin.readline().split())
A = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(M):
    s, e = map(int, sys.stdin.readline().split())
    A[s].append(e)
    A[e].append(s)


def DFS(v):
    visited[v] = True
    for i in A[v]:
        if not visited[i]:
            dfs(i)

count = 0
for i in range(1, N+1):
    if not visited[i]:
        count+=1
        DFS(i)

print(count)

 

2) 해설

(1) 패키지 Import

import sys
sys.setrecursionlimit(10000)

파이썬 내장 함수인 input()보다 빠르게 값을 입력받기 위해 sys 라이브러리를 사용하였다.

또한 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회이므로 재귀의 최대 깊이를 10000으로 늘려주었다.

 

(2) 입력받기

N, M = map(int, sys.stdin.readline().split())
A = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(M):
    s, e = map(int, sys.stdin.readline().split())
    A[s].append(e)
    A[e].append(s)

노드의 개수(N)와 엣지의 개수(M)를 입력받고, 인접 리스트(A)와 방문 리스트(visited)를 초기화한다.

엣지의 개수만큼 for문을 순회하면서 인접 리스트를 생성한다.

이때, 방향이 없는 그래프이므로 양방향 엣지로 구현한다.

 

(3) DFS 구현

def DFS(v):
    visited[v] = True
    for i in A[v]:
        if not visited[i]:
            dfs(i)

인자로 들어온 노드에 대해 방문 리스트를 체크한다.

해당 노드에 대한 인접 리스트의 요소들 중 방문하지 않은 노드에 대해 재귀 방식으로 DFS를 수행한다.

 

(4) 출력하기

count = 0
for i in range(1, N+1):
    if not visited[i]:
        count+=1
        DFS(i)

print(count)

모든 노드를 순회하면서 만약 방문하지 않은 노드가 있다면 count를 1 증가시키고 DFS를 수행한다.

여기서 count 변수는 연결 요소를 뜻한다.

 

✅ 정답 확인

---

포스팅한 내용에 대한 조언/지적/피드백 모두 환영입니다!

읽어주셔서 감사합니다^.^