[백준 11724] 연결 요소의 갯수

연결 요소의 갯수

문제설명

첫 줄에 노드의 수 , 간선의 수를 입력 받는다.
총 연결된 요소의 갯수를 출력한다.

알고리즘

1. 노드의 수와 간선의 수를 입력 받는다.
2. 연결 여부를 나타낼 graph인 2차배열, 방문여부를 나타낼 배열을 N+1크기만큼 만든다.
3. 간선의 연결 관계를 입력 받고, (2,1)인경우 (1,2)에도 값을 넣는다.
4. 반복적으로 조회하여 방문하지 않은 경우 (False인 경우) dfs 함수에서 동작한다.
5. 연결의 수를 출력시킨다.

---

import sys
sys.setrecursionlimit(10000)

# 깊이 우선 탐색
def DFS(v):
    visited[v]=True
    for e in graph[v]:
        if not visited[e]:
            DFS(e)

N, M = map(int, sys.stdin.readline().split()) #노드의 수와 간선의 수 입력 받기
graph=[[] for _ in range(N+1)] #graph 초기화
visited = [False] * (N+1) #방문 여부 초기화
count =0 #결과 값

for _ in range(M):
    u,v = map(int, sys.stdin.readline().split()) #연결 간선 입력 받기
    graph[u].append(v) #간선 값 입력
    graph[v].append(u) #간선 값 입력


for j in range(1, N + 1):
    if not visited[j]: #방문하지 않은 경우 dfs 시작
        DFS(j)
        count += 1

print(count)

고찰

이번 문제는 언어를 파이썬으로 dfs를 풀자니 새로운 부분들이 있었다.
2차원 배열선언 및 초기화 방법을 다시 공부할 필요가 있었던 문제였다.