BOJ: 연결 요소의 개수 - 1475번

11724번: 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

내가 작성한 코드

# https://www.acmicpc.net/problem/11724
# 연결 요소의 개수 
import sys 
def bfs(start_v): 
	discovered = [start_v] 
    queue = [start_v] 
    while queue:
    x = queue.pop(0)
    if x in graph:
    	for w in graph[x]:
        	if w not in discovered:
            	discovered.append(w)
                queue.append(w)
	return discovered

n, m = map(int, sys.stdin.readline().split()) 
graph = dict() 
for _ in range(m): 
	u, v = map(int, sys.stdin.readline().split()) 
    if u in graph: 
    	graph[u].append(v) 
    else: 
    	graph[u] = [v]
	if v in graph:
    	graph[v].append(u)
	else: 
    	graph[v] = [u] 

total = 0 
visited = [] 
for i in range(1, n+1): 
	if i not in visited: 
    	visited.extend(bfs(i)) 
        total += 1 
print(n - len(visited) + total)

 

풀이

n, m = map(int, sys.stdin.readline().split()) 
graph = dict() 
for _ in range(m): 
	u, v = map(int, sys.stdin.readline().split()) 
    if u in graph:
    	graph[u].append(v) 
    else: 
    	graph[u] = [v] 
	if v in graph: 
    	graph[v].append(u) 
	else: 
    	graph[v] = [u]

이 문제를 풀면서 문제를 꼼꼼히 읽어야 한다는 걸 느꼈다. 지문에는 생각보다 많은 힌트가 있다. 같은 간선은 한 번만 주어진다고 쓰여져 있어서 딕셔너리에 저장해줄 때 key가 u일 때, key가 v일 때 둘 다 저장해줬다.

total = 0
visited = [] 
for i in range(1, n+1): 
	if i not in visited: 
	visited.extend(bfs(i)) 
    total += 1 
print(n - len(visited) + total)

그 다음에는 일반적인 느낌으로.. 그래프를 순회하면서 방문한 배열에 없으면 bfs 함수를 통해 탐색하고, 탐색한 discovered 배열을 visited 배열에 추가한다. 마지막 출력문이 핵심인데, 이 글의 답변을 통해 알았다. 이어지는 간선이 없다고 정점이 없는게 아니다. 전체 정점의 개수에서 방문한 요소의 개수를 빼고, total에 저장해둔 이어진 선의 개수를 더해서 출력했다.