문제 링크
https://www.acmicpc.net/problem/11724
문제 유형
DFS/BFS
🌈문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
6 5
1 2
2 5
5 1
3 4
4 6출력
첫째 줄에 연결 요소의 개수를 출력한다.
2💡 아이디어
가장 먼저 든 생각은 유니온 파인드(Union Find) 개념을 이용하는 것이다. 모든 노드의 부모를 자기 자신으로 설정하고, 왼쪽 요소를 트리의 루트로 삼아 트리의 계층을 하나씩 늘려 가는 방식으로 풀이하려고 하였다.
하지만 이 문제는 6개의 노드가 있다고 해서 1부터 시작하여 6까지의 노드가 모두 나올지 알 수 없는 상황이고, 모든 리스트를 생성한다고 가정하였을 때 최악의 상황으로는 1, 500, 100000과 같이 노드 번호가 주어지는 것이다. 그럼 자기 자신으로 설정한 재귀함수를 돌리는 데에는 얼마 시간이 들지 않지만 초기화 리스트를 불필요하게 길게 가져가야 하기 때문에 좋은 풀이라고 할 수는 없을 것이라고 생각된다.
다음으로 할 수 있는 생각은 바로 BFS를 이용하는 것이다.
모든 노드를 탐색하면서 방문한 곳은 방문처리를 해 주고, 한 싸이클의 방문이 모두 끝나면 정답 값을 하나씩 올려주면 되는 것이다.
👨💻 코드 작성
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]정점의 개수만큼 이차원 배열을 만듭니다. 그럼 총 N + 1개의 노드가 생성됩니다.
1번 노드부터, N번 노드까지의 인덱스를 지정할 수 있다.
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)입력값을 하나씩 받아 해당 graph의 인덱스에 인접한 노드를 추가해준다.
visited = [False] * (1 + N)
count = 0
for i in range(1, N + 1):
if not visited[i]:
if not graph[i]:
count += 1
visited[i] = True
else:
bfs(i)
count += 1
print(count)만약 방문하지 않은 노드에 방문한다면 검사를 시작하여 준다.
여기서, if not graph[i]처럼 빈 노드에 들어갔다면, 독립되어 하나로 떨어져 있는 친구이므로 그 친구는 방문처리를 해주고 하나의 정답으로 처리해준다.
그리고 만약 연결된 노드가 있다면 bfs를 이용하여 연결된 모든 노드들을 방문해주어야 한다. bfs가 끝나게 되면 정답을 하나 늘려주는 것이다.
def bfs(start):
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
for i in graph[node]:
if not visited[i]:
visited[i] = True
queue.append(i)짜잔~ bfs이다.
큐에 해당 노드값을 넣어준다. 그리고 방문처리를 완료해준 다음 연결된 모든 노드들을 큐에 넣어 하나씩 요소들을 검사해주는것이다. 매우 기본적인 bfs의 코드이다.
해당 문제는 Graph 노드를 만들어 주는 아이디어를 생각해낸다면 Bfs의 기본적인 코드를 이용하여 쉽게 풀 수 있었던 문제인것 같다. 모든 곳에 방문하여 count를 해야 할 때 Bfs를 생각해내보자!
