[백준] 11724번 연결 요소의 개수 - Python / 알고리즘 기초 2/2 - 그래프 1

---

---

---

💡 문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

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

---

💭 접근

연결된 서로 다른 그래프가 몇개인지 구하는 문제이다.

예제 1을 예를 들어 그래프를 그려보자.

이처럼 이어지지 않은 서로 다른 그래프가 2개 있다.

이를 찾기 위해 방문하지 않은 정점을 시작으로 DFS를 호출하여주면 서로 다른 그래프의 개수를 알아낼 수 있다.

ans = 0
for i in range(1, n + 1):
    if not visited[i]:
        ans += 1
        dfs(i)

i = 1, visited = [False, True, True, False, False, True, False] -> ans = 1
i = 3, visited = [False, True, True, True, True, True, True] -> ans = 2 (종료)

---

📒 코드

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

def dfs(start):
    visited[start] = True

    for v in graph[start]:
        if not visited[v]:
            dfs(v)

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
visited = [False for _ in range(n + 1)]

ans = 0
for i in range(1, n + 1):
    if not visited[i]:
        ans += 1
        dfs(i)

print(ans)

---

💭 후기

방문 여부(visited 배열)를 어떻게 활용할 지 떠올렸다면 쉽게 해결할 수 있는 문제.

---

🔗 문제 출처

https://www.acmicpc.net/problem/11724

---