[구름톤 챌린지] Day16 : 연합

소스 코드

from collections import deque
n, k = map(int, input().split())
#undirected graph
graph = [[] for _ in range(n+1)]
#is undirect connected?
sc = [[False for _ in range(n+1)] for _ in range(n+1)]
for _ in range(k):
	a, b = map(int, input().split())
	if not sc[b][a]:
		sc[a][b] = True
	else:
		#undirected connected graph
		graph[a].append(b)
		graph[b].append(a)
visited = [False for _ in range(n+1)]
unions = 0
for i in range(1, n+1):
	# i : start node
	if not visited[i]:
		unions += 1
		q = deque([i])
		visited[i] = True
		while q:
			now = q.popleft()
			for i in graph[now]:
				if not visited[i]:
					visited[i] = True
					q.append(i)
print(unions)

문제 풀이

0. 단방향 그래프의 간선을 표시할 행렬과 양방향 그래프의 간선을 저장할 행렬을 별개로 준비한다.

1. 간선들을 입력받은 후 그래프 행렬에 표시한다. (이 그래프 행렬은 단방향 그래프의 간선들을 표시한다.)

2. 입력 받은 간선의 역방향 간선이 존재한다면, 그 두 정점은 양방향 연결이 되었다는 뜻이므로 양방향 그래프에 이 간선을 추가한다.

3. 그렇게 양방향 연결 그래프가 완성되었다면, 전형적인 Connected Component를 찾는 문제가 된다.

4. 너비 우선 탐색으로 해결하자.

느낀 점

처음에 생각했던 대로 코드를 구성해서 제출했더니 한 번에 정답이 됐다. 매우 뿌듯했다.

이 것보다 더 좋은 코드가 있을까? 정답 코드는 내 문제 해결 방향과 매우 비슷했다.