[백준 11724번] 연결 요소의 개수

 

# 요즘 알바도 새로 시작하고 머신러닝 스터디도 진행하느라 너무 바빠 정말 오랜만에 백준 문제를 풀어보았다.

# DFS, BFS를 사용한 알고리즘 문제

 

-- 정답 코드

 

# 연결 요소의 개수

import sys
from collections import deque
# 정점의 개수 N
# 간선의 개수 M
N, M = map(int, sys.stdin.readline().split())

gansun = {}

for i in range(1, N+1):
    gansun[i] = set()

for _ in range(M):
    a, b = map(int,sys.stdin.readline().split())
    if a in gansun:
        gansun[a].add(b)
    else:
        gansun[a] = set([b])
    if b in gansun:
        gansun[b].add(a)
    else:
        gansun[b] = set([a])

def DFS(graph):
    component = 0
    count = 0
    while component < N:
        stack = deque([list(gansun.keys())[0]]) # 남아 있는 딕셔너리의 처음 키부터 시작
        visited = []
        while stack:
            n = stack.pop()
            if n not in visited: # 아직 방문 안했다면 추가
                visited.append(n)
                temp = list(graph.get(n,set()) - set(visited))
                temp.sort(reverse = True) # LIFO 구조를 만들기 위해 역순으로 넣어준다
                stack += temp
        component += len(visited)
        count += 1
        for i in visited:
            graph.pop(i)
    return count

print(DFS(gansun))

기본적인 DFS 알고리즘을 활용해 문제를 풀었는데 BFS 알고리즘을 활용해도 같은 방법으로 문제를 풀 수 있을 것이다. 처음에는 gansun 딕셔너리에 입력받지 않은 정점의 빈 set을 입력해 주지 않아서 IndexError가 발생했었는데 기본적으로 1 ~ N 까지의 빈 set을 딕셔너리에 추가한 후 딕셔너리를 만들어주니 올바른 정답이 도출되었다.

 

기본적인 DFS 알고리즘에서 사용하는 while 반복문 바깥에 component의 개수를 세어 전체 연결 요소를 count 할 수 있도록 while 문을 만들어 주었다. 

 

문제에서 제시한 연결 요소라는 것은 이어지지 않은 연결 고리들의 개수를 의미한다. 예를들어 1-2-3, 4-5 이면 연결 요소는 2개, 1-2, 3-4, 5 이면 연결 요소는 3인 것이다. 이를 작성하고 변수 명을 다시 보니 코드에서 사용한 component 변수와 count 변수를 바꿔서 작성했으면 더 좋았을 것이라는 생각이 든다. 

 

 

오늘은 주어진 정점과 간선을 통해 연결 요소의 개수를 구해보았다.