[백준] 11724번 연결 요소의 개수, 파이썬 문제풀이

문제

백준 11724번 연결 요소의 개수를 해결했습니다. 노드와 간선의 수가 주어지면 연결되어 있는 연결 요소의 개수를 찾는 문제입니다. DFS를 활용해서 해결했습니다.

https://www.acmicpc.net/problem/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를 진행합니다. DFS를 진행하는 횟수가 곧 연결 요소의 개수가 됩니다.

 

이번 문제는 큰 어려움이 없기 때문에 코드로 바로 확인하고 마무리하겠습니다.

def DFS(n):
    visited[n]=1
    for i in node[n]:
        if(visited[i]==0):
            visited[i]=1
            DFS(i)


N, M = map(int, input().split())
node = [[]*(M+1) for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    node[a].append(b)
    node[b].append(a)

visited = [0]*(N+1)

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

print(result)

 

정리

DFS를 활용하는 문제였습니다.