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

문제출처] https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

---

문제요약

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

풀이

파이썬에서는 딕셔너리 자료구조를 이용하면 그래프를 손쉽게 구현할 수 있다.

n, m = map(int, input().split())
graph = {i: [] for i in range(1, n+1)}
visted = [0 for _ in range(n+1)]

for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

입력 받기 전 그래프의 key 값을 1부터 n까지로, value값을 list로 초기화해준다.

입력을 받아 key 값에 해당하는 리스트에 value를 추가해준다. 간선은 중복이 필요없으므로 중복을 제거해주어도 되지만 실시하지는 않았다. 

---

def traversals(start, graph):
  visted[start] = 1
  queue = [start]
  while queue:
    v = queue.pop(0)
    for node in graph[v]:
      if visted[node] == 0:
        visted[node] = 1
        queue.append(node)

순회는 BFS를 이용하여 구현하였다. BFS는 queue를 활용하여 구현할 수 있다. 

c/c++로 구현한 DFS/BFS https://zero-rabbit.tistory.com/20

---

소스코드는 Python 3으로 작성되었습니다.

n, m = map(int, input().split())
graph = {i: [] for i in range(1, n+1)}
visted = [0 for _ in range(n+1)]
result = 0

for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

def traversals(start, graph):
  visted[start] = 1
  queue = [start]
  while queue:
    v = queue.pop(0)
    for node in graph[v]:
      if visted[node] == 0:
        visted[node] = 1
        queue.append(node)

for node in graph:
  if visted[node] == 0:
    traversals(node, graph)
    result += 1

print(result)