문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
제한사항
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
첫째 줄에 연결 요소의 개수를 출력한다.
문제를 보고 든 생각
당최 문제가 뭘 원하는지 이해가 안 갔다.내가 아는 연결 요소라 함은 정말 별 게 없이 그냥 연결 되어 있는 요소다.강한 연결이 있다고 할 때는 순환이 필요하지만, 연결되어 있다는 건 정말 그저 연결되어 있으면 되는 거다.
근데 이렇게 그래프 탐색 문제로 만나니까 뭘 어떻게 해야 하나 싶었다.
나의 아이디어
연결 요소인 건 알겠는데 진짜 뭘 어떻게 하라는 건지 예제를 보고도 이해가 안 갔다.결국 검색을 통해 이 문제를 해결했다.
검색을 통해 알게 된 내용
억울해서 죽겠다.사실 처음에는, 검색을 해서 풀이를 봐도 이게 왜 연결 요소의 개수를 구하는 건지 이해가 가지 않았다.
그런데 계속 반복해서 풀다보니까 이제야 이해할 수 있었다.말이 연결 요소의 개수지 그냥 bfs 혹은 dfs가 함수에 들어갔다가 나오는 횟수를 구하는 것과 같다.
한번 함수 안에 들어갈 때 연결되어 있는 요소들을 모두 체크하고 나오는데 이게 연결 요소 1개이기 때문에
함수 안에 들어갔다 나오는 횟수를 구하면 된다.
하하하.
검색을 통해 알게 된 풀이
1. bfs를 이용한 풀이
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().rstrip().split())
graph = [[] for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]
for i in range(m):
u, v = map(int, input().rstrip().split())
graph[u].append(v)
graph[v].append(u)
def connected(vertex):
q = deque([vertex])
visited[vertex] = True
while q:
now = q.popleft()
for node in graph[now]:
if not visited[node]:
visited[node] = True
q.append(node)
answer = 0
for v in range(1, len(graph)):
if not visited[v]:
connected(v)
answer += 1
print(answer)
정말 복잡해 보인다.
나도 이 문제를 완전히 이해하기 전까지 즉, 이 문제가 원하는 게 함수 안에 들어갔다가 나온 횟수라는 걸 파악하기 전까지는 진짜 복잡해 보였다.
그런데 보다보면 정말 별 게 없다.
connected 함수 위로는 모두 입력을 받기 위한 코드들이다.
함수부터 코드의 흐름은 아래와 같다.
a. 정점 1부터 n + 1까지 탐색하기 위해 for문을 돌린다.
b. 현재 정점과 연결된 간선들을 탐색한 적이 없다면 탐색을 시작한다.
c. connected 함수(bfs) 안에서 v와 연결된 모든 간선들을 탐색하여 연결된 정점들에 방문 체크를 해준다.
v에 연결되어 있던 모든 정점에 체크가 완료되었다면 함수에서 빠져나와 answer에 1을 더해준다.
d. 1 ~ 4번 과정을 v가 n + 1이 될 때까지 반복한다.
2. dfs를 이용한 풀이
import sys
sys.setrecursionlimit(3000)
input = sys.stdin.readline
n, m = map(int, input().rstrip().split())
graph = [[] for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]
for i in range(m):
u, v = map(int, input().rstrip().split())
graph[u].append(v)
graph[v].append(u)
def connected(v):
visited[v] = True
for node in graph[v]:
if visited[node] == False:
connected(node)
answer = 0
for i in range(1, len(graph)):
if visited[i] == False:
connected(i)
answer += 1
print(answer)전체적인 흐름은 bfs와 완전히 일치한다.
다만 차이가 있다면, sys의 setrecursionlimit와 deque의 유무이다.
이 문제는 방문 체크만 하면 되는 문제라서 dfs, bfs 둘 중 어느 것을 쓰든 상관이 없기에
stack 방식을 활용하는 dfs가 내 생각에는 더 가볍고 괜찮은 것 같다.
(하지만 백준 기준으로 실제로는 bfs 방식이 더 가볍고 빨랐다.)
재귀 제한을 다시 설정해준 이유는 default 값으로 제출을 하니 런타임 에러가 떠서 재귀 제한을 늘려서 설정해주었다.
느낀 점
이 문제를 반복해서 풀어보며 느낀 건, 물론 내가 문제에 대한 어려움을 느껴서 알고리즘을 떠올리지 못하는 경우도 있겠지만 어쩌면 문제에 대한 이해력이 부족한 것 같다는 생각이 들었다.
문제를 읽고 어떤 걸 요구하고 있는지 파악하는 능력이 부족한 것 같다.
