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

 

✔️ 풀이 방법

n,m을 받은 후 n*n의 graph 표를 만든다.

이후 u와 v를 받아서 어떤 간선끼리 연결되어 있는지 graph에 기록한다.

연결 요소의 개수를 구하는 것은 인접한 정점으로 이루어진 그래프 개수를 세는 것과 같다.

 

✔️ 코드

import sys
sys.setrecursionlimit(10**6)
n,m = map(int, sys.stdin.readline().split())
graph = [[]for _ in range(n+1)]
visited = [False]*(n+1)
cnt=0

for _ in range(m) : 
    u,v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

# DFS
def dfs(v) : 
    visited[v] = True
    for i in graph[v] :
        if not visited[i] : # 방문하지 않은 노드라면
            dfs(i) # 재귀 호출

for i in range(1,n+1) :
    if not visited[i] : # 해당 정점이 방문하지 않았다면
        dfs(i)
        cnt += 1

print(cnt)

 

✔️ 연결요소

1) 정의 : 그래프를 한 개 제시했는데, 이 그래프가 여러 component로 뚝뚝 떨어진 그래프들일 수 있다. 아래의 그림처럼 나누어진 각각의 그래프를 연결 요소라고 한다. 조건은 아래와 같다.

• 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
• 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

 

2) 오류 : 런타임에러(RecursionError)

dfs를 쓰면 간혹 발생하는 에러.

두번째 줄 코드를 사용해서 탐색 깊이를 조절해준다.