[백준/Python] 11724번 : 연결 요소의 개수

문제 정보

제목 : 연결 요소의 개수

번호 : 11724번

사용 언어 : Python

문제 링크

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) 같은 간선은 한 번만 주어진다.

 

출력

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

 

입출력 예제

---

나의 풀이

재귀에 제한이 걸려 설정하는 코드를 적었고, 입력에 대한 시간을 줄이기 위해 sys.stdin.readline()을 사용합니다. 정점의 개수와 간선의 개수를 입력받아 N, M에 각각 정수형으로 변환한 후 저장합니다. 방문 여부를 체크할 수 있도록 N+1 길이만큼 False가 저장되어있는 리스트를 생성합니다. 간선의 개수인 M번 반복하는 for루프를 이용해 간선의 양 끝점 u와 v를 입력받아 리스트형 딕셔너리에 저장합니다. 이때 그래프는 방향 없는 그래프이므로 u와 v에 해당하는 키에 각각 값을 저장합니다.

DFS 함수를 정의하여 해당 노드를 인덱스로 하여 방문 여부 체크 리스트를 True로 바꾸고, graph[start]에 하나씩 접근하는 for 루프를 이용해 방문하지 않은 노드에 하나씩 재귀적으로 DFS 함수를 실행할 수 있도록 합니다. 함수까지 정의했으면 이제 연결 요소의 개수를 구할 것입니다. 1부터 N+1까지 반복하는 for루프를 이용해 visited_node[i]가 방문하지 않은 노드라면 count를 1 증가 시키고 DFS(i)를 수행합니다.

모든 반복이 끝나면 count를 출력합니다.

 

코드

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

graph = defaultdict(list)
count = 0 # 연결 요소의 개수

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

visited_node = [False] * (N + 1) # 방문 여부 체크 리스트

# 간선의 양 끝점을 입력받아 그래프를 딕셔너리로 표현함
for i in range( M ) :
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

def DFS( start ) :
    visited_node[start] = True

    for i in graph[start] :
        if not visited_node[i] :
            DFS(i)

# 연결 요소의 개수 구함
for i in range(1, N+1) :
    if not( visited_node[i] ):
        count +=1
        DFS(i)

print(count)