[CodingTest] BOJ111724 연결요소 ( DFS, UNION-FIND ) With 파이썬

11724번: 연결 요소의 개수

 

 

◎문제풀이

무방향 그래프의 연결요소의 개수를 구하는 문제이다. 연결요소는 끊어짐 없이 연결된 그래프를 의미한다. 무방향 그래프에서 연결요소를 구하는 대표적인 알고리즘은 UNION-FIND 알고리즘이다. 

 

[Algorithm] Union-Find 알고리즘이란? ( with 서로소 집합 자료구조 )

 

UNION-FIND가 아니더라도 DFS로 풀 수 있는 문제이다.  DFS를 모든 노드에서 탐색한다. 이때 방문이력을 테이블로 관리하여 방문한 노드는 탐색에서 제외한다. DFS로 탐색된 노드들은 하나의 연결된 그래프이다. 탐색되지 않은 노드는 연결된 그래프와 분리됨을 의미한다. DFS 탐색이 끝나고 탐색되지 않은 노드가 있다면 카운트하고 해당 노드부터 DFS탐색을 시도한다.

 

 

◎코드

 

UNION-FIND 알고리즘

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
parent = [0] * (n+1)

#부모테이블 초기화
for i in range(1,n+1) :
  parent[i] = i 

#find 
def find(parent,x) :
  if parent[x] != x : parent[x] = find(parent,parent[x]) #바로 루트로 갈 수 있도록 경로압축
  return parent[x]

#union
def union(parent,a,b) :
  a_root = find(parent,a)
  b_root = find(parent,b)
  if a_root != b_root : 
    if a_root > b_root : parent[a_root] = b_root
    else : parent[b_root] = a_root

#UNION-FIND 알고리즘 시작
for _ in range(m) :
  a,b = map(int,input().split())
  union(parent,a,b)

#결과리스트 생성
result = []
for i in range(1,n+1) :
  result.append(find(parent,i))

print(len(set(result))) #set자료구조로 중복제거

 

DFS 알고리즘

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

#무방향 그래프
for _ in range(m) :
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

#dfs
def dfs(graph,x,visited) :
  visited[x] = True

  for next in graph[x] :
    if not visited[next] :
      dfs(graph,next,visited)

#DFS 호출
count = 0
for i in range(1,n+1) :
  if not visited[i] : 
    dfs(graph,i,visited)
    count += 1

print(count)