[파이썬/Python] 백준 11724번: 연결 요소의 개수

숨·2024년 7월 20일

알고리즘 문제 풀이

목록 보기

38/105

📌 문제 : 백준 11724번

📌 문제 탐색하기

N : 정점의 개수 ( $1 ≤ N ≤ 1,000$ )
M : 간선의 개수 ( $0 ≤ M ≤ \frac{N×(N-1)}{2}$ )
u, v: 간선의 양 끝점 ( $1 ≤ u, v ≤ N, u ≠ v$ )

✅ 입력 조건
1. N, M 공백 구분해 입력
2. M번 반복해 u, v 간선 정보 입력
3. 같은 간선은 1번만 입력됨
4. 방향 없는 그래프
✅ 출력 조건
1. 연결 요소의 개수 출력

연결 요소(Connected Component)의 개수는 연결된 묶음들이 몇 개인지를 의미한다.
이전 순열 사이클 문제처럼 BFS를 통해 연결된 모든 노드를 탐색하고, BFS를 수행한 횟수만큼 출력하면 된다.

방향 없는 그래프이기 때문에 입력 받은 연결 정보를 그래프에 넣을 때, 두 정점 모두에 서로를 연결 노드로 입력한다.

큐를 통해 BFS를 구현하고, 큐에 각 노드를 넣어 연결된 모든 노드를 탐색한다.

방문 리스트를 돌면서 방문 안한 노드가 있다면 BFS를 수행해서 그 수행 횟수를 계산하고 출력한다.

가능한 시간복잡도

그래프 저장 → $O(M)$
BFS 수행 → $O(N + M)$
전체 그래프 돌기 → $O(N)$

최종 시간복잡도
$O(N + M)$ 으로,
최악의 경우, N이 최대 1000일 때도 1초 내로 계산이 가능할 것 같다.

알고리즘 선택

그래프에 연결 정보를 저장하고 BFS 수행 횟수 계산하기

📌 코드 설계하기

BFS 정의
1-1. 방문 처리
1-2. 큐가 빌 때까지 반복
1-3. 해당 노드 연결 정보 확인
1-4. 방문 안했다면 방문 처리
N, M 입력
그래프 정의
M번 반복해 u, v 입력받아 그래프에 저장
방문 리스트 정의
연결 요소 세는 변수 정의
BFS 수행
원하는 형식으로 출력

📌 시도 회차 수정 사항

1회차

### 수정 전
# BFS 수행
for i in range(N+1):
    if not visited[i]:
        bfs(i)
        count += 1
        
### 수정 후
# BFS 수행
for i in range(1, N+1):
    if not visited[i]:
        bfs(i)
        count += 1

결과
원하는 답에서 1이 더 큰 답이 나왔다. BFS를 수행할 때 없는 노드 0부터 수행해서 연결 요소가 하나 더 크게 나온 것이다.
노드 1부터 N까지만 BFS를 수행하도록 하여 원하는 답을 얻었다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# BFS 정의
def bfs(x):
    queue = deque([x])
    # 방문 처리
    visited[x] = 1
    # 큐가 빌 때까지 반복
    while queue:
        y = queue.popleft()
        for i in graph[y]:
            if not visited[i]:
                # 방문 처리
                visited[i] = 1
                queue.append(i)


# N, M 입력
N, M = map(int, input().split())

# 그래프 정의
graph = [[] for _ in range(N+1)]

# M번 반복해 u, v 입력받아 그래프에 저장
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# 방문 리스트 정의
visited = [0] * (N+1)

# 연결 요소 세는 변수 정의
count = 0

# BFS 수행
for i in range(1, N+1):
    if not visited[i]:
        bfs(i)
        count += 1

# 정답 출력
print(count)