[baekjoon] 백준 11724번(파이썬): 연결 요소의 개수

문제

11724번: 연결 요소의 개수

- 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 문제이다.

-정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 

- M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

- 연결 요소의 개수를 출력하라.

알고리즘

- dfs 탐색을 통해 문제를 수행한다.

- 재귀 함수를 쓰기 위해 허용 깊이를 수동으로 늘려준다.

- 노드 탐색 여부 리스트와 2차원 리스트의 맵 정보를 입력받아 표현한다.

코드

import sys
sys.setrecursionlimit(10**6) # 재귀 허용 깊이를 수동으로 늘려주는 코드

# dfs 탐색
def dfs(x):

    visited[x] = True

    # 탐색하지 않은 연결된 노드 찾기
    for i in range(1, n+1):
        if graph[x][i] == 1 and visited[i] == False:
            dfs(i)


n, m = map(int, sys.stdin.readline().split())

# 노드 탐색 유무
visited = [False] * (n + 1)

graph = [[0] * (n + 1) for i in range(n + 1)]
# 2차원 리스트의 맵 정보를 입력 받는다.
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[b][a] = graph[a][b] = 1

cnt = 0

# 현재 위치에서 DFS 수행
for i in range(1, n + 1):
    if visited[i] == False:
        dfs(i)
        cnt += 1
print(cnt)

github

junjange/CodingTest