문제

풀이

먼저, 연결요소란 그래프의 개수와 같다. 정점 사이에 겹쳐진게 없고, 나누어진 각각의 그래프를 연결 요소라고 생각하면 된다. 연결 요소는 dfs나 bfs탐색으로 구할 수 있다.

graph는 2차원 배열로 연결된 정보를 얻을 수 있음. visited 배열은 정점에 방문했는지 확인하기 위한 배열로 False로 초기화.

dfs함수에서는 방문하지 않은 곳을 dfg해주고 반복 끝에 result값에 1을 더하고 출력하면 됨.

DFS ( Depth-First Search )

• 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택(Stack) 자료구조를 이용하여 구현

과정

1. 노드를 스택에 삽입하고 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으며 그 인접 노드를 스택에 넣고 방문 처리한다.
   2.1. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

이 과정을 수행할 수 없을 때까지 반복한다.

예시 코드

visited = [False] * 4

graph = [
[],
[1,3],
[2],
[2,3]
]

def dfs(graph, v, visited):
  visited[v] = True # 현재 노드 방문 처리
  print(v, end = ' ')
    
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)
         
dfs(graph, 1, visited)

# 결과
1 3 2

코드

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
visited=[False]*(n+1)
count = 0

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

def dfs(v):
  visited[v]=True
  for i in graph[v]:
    if not visited[i]:
      dfs(i)
      
for i in range(1,n+1):
  if not visited[i]:
    dfs(i)
    count += 1
    
print(count)

결과