문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
제한사항
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.첫째 줄에 연결 요소의 개수를 출력한다.
문제를 보고 든 생각
너무나도 절망적이었다.BFS에 좀 익숙해졌다 싶어서 호기롭게 문제를 선택했는데, 또 다시 비참함을 겪었다.문제에 손을 못 대겠을 때에는 어떻게 해야 하는지 알고 싶다.
검색을 통해 알게 된 내용
BFS를 처음 하는 건 아니지만, 정말 여전히 새롭게 느껴진다는 게 너무나도 분하다.풀이를 볼 때마다 사람들은 자꾸 새로운 방식으로 문제를 해결해낸다.나는 왜 떠오르지가 않는 걸까.문제를 보고 어떻게 이걸 풀어내야 할지 감이 잡히지 않는 걸까.
검색을 통해 알게 된 풀이
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
answer = 0
for i in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
visited = [False] * len(graph)
def connecting(graph, v, visited):
q = deque([v])
visited[v] = True
while q:
now = q.popleft()
for node in graph[now]:
if visited[node] == False:
q.append(node)
visited[node] = True
for node in range(1, len(graph)):
if visited[node] == True: continue
connecting(graph, node, visited)
answer += 1
print(answer)
실상은 어렵지 않은 코드이지만, 왜 떠오르지가 않을까.
문제 이해가 잘 안 돼서 그러는 걸까.
코드의 흐름은 아래와 같다.
1. 무방향 그래프이기 때문에 u, v를 입력받으면서 미리 만들어 놓은 그래프 안에 u, v를 저장할 때 서로가 서로를 향하게끔 저장해두는 것이 중요하다. 방향 그래프라면 문제에서 주어지는 방향대로 append 해주면 된다.
2. 핵심인 bfs 부분이다. 핵심이지만, 너무나도 기초적인 bfs의 흐름이다.
하지만 아래의 단계가 떠오르지 않았다.
for node in graph[now]:
if visited[node] == False:
q.append(node)
visited[node] = True- 현재의 정점과 연결되어 있는 node에 방문한 적이 없다면 q에 node를 넣어주고 방문 체크를 해준다.
3. 이 부분도 핵심적이다. 그러나 떠오르지 않았다.
for node in range(1, len(graph)):
if visited[node] == True: continue
connecting(graph, node, visited)
answer += 1보통 그래프 상에서 덩어리의 개수를 셀 때 이런 방식으로 했던 것이 기억난다.
몇 개월 전에 했지만 금세 까먹었다.
느낀 점
검색으로 찾은 코드를 보고 이해가 빨리 됐다는 건 불행 중 다행이다.
문제를 붙잡고 계속 고민하는 것도 한계가 있지 않을까라는 생각이 들면서도 검색을 하면 좌절한다.
중간을 모르겠다.
