[이것이 코딩테스트다] 25일차 - 그래프이론(1)

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 10 그래프이론

해당 글의 모든 사진자료는 아래 강의에서 가져온것입니다.

 

서로소 집합

서로소 집합이란 공통 원소가 없는 두 집합을 의미한다

 

서로소 집합 자료구조

• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기위한 자료구조
• union, find 두가지 연산으로 조작가능
  • union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • find: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

서로소 집합 알고리즘

1. union (합집합) 연산을 확인하여 서로 연결된 A, B노드를 확인한다
   1. A,B 노드의 루트노드 A', B'를 각각 찾는다
   2. A', B'를 부모 노드로 설정한다 (둘 중 큰수가 작은수를 가리키도록)
2. 모든 union 연산을 처리할때까지 반복한다

예시 

union 1,4 , union 2,3, union 2,4 , union 5,6 일때

노드	1	2	3	4	5	6
부모노드	1	2	3	4	5	6

처음에는 각 노드의 부모노드를 자기 자신으로 설정한다

 

union 1,4  -> A' = 1 B' = 4

A'가 더 작은 값이므로 4의 부모노드를 1로 설정 (둘 중 큰수가 작은수를 가리키도록)

노드	1	2	3	4	5	6
부모노드	1	2	3	1	5	6

 

union 2,3  -> A' = 2 B' = 3

A'가 더 작은 값이므로 3의 부모노드를 2로 설정 (둘 중 큰수가 작은수를 가리키도록)

노드	1	2	3	4	5	6
부모노드	1	2	2	1	5	6

 

union 2,4  -> A' = 2 B' = 1

B'가 더 작은 값이므로 2의 부모노드를 1로 설정 (둘 중 큰수가 작은수를 가리키도록)

노드	1	2	3	4	5	6
부모노드	1	1	2	1	5	6

 

union 5,6  -> A' = 5 B' = 6

A'가 더 작은 값이므로 6의 부모노드를 5로 설정 (둘 중 큰수가 작은수를 가리키도록)

노드	1	2	3	4	5	6
부모노드	1	1	2	1	5	5

 

모든 union 연산을 마친 후 연결성을 보면 다음과 같다

이코테 272p

 

이때 2의 부모노드가 1이므로, 노드 3의 루트를 찾기 위해서는 부모노드인 2로 이동하고 이 노드의 부모노드를 확인하여 노드 1로 접근해야한다

-> 서로소 집합의 루트를 찾기 위해서는 재귀적 방법을 사용해야 한다는 것!

 

서로소 집합 알고리즘 소스코드 (기본)

# 특정 원소가 속한 집합을 찾기 -> x의 루트노드를 반환한다.
def find_parent(parent, x):
    #루트 노드를 찾을때까지 따라들어가며 재귀호출 (루트노드는 자기자신이 부모노드이므로)
    if parent[x] != x: #루트노드가 아니면 
        return find_parent(parent, parent[x]) #재귀호출 
    return x #루트노드일때 자기자신을 반환 

#두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
	#각각의 루트노드를 찾는다.
    a = find_parent(parent, a) 
    b = find_parent(parent, b)
    if a<b: #두 노드중 큰 노드의 부모를 바꿔준다.
        parent[b] = a
    else:
        parent[a] = b

#노드와 간선의 개수 입력
v,e = map(int, input().split())
parent = [0] * (v+1) #부모테이블

#초기상태 - 부모를 자기자신으로 초기화
for i in range(1,v+1):
    parent[i] = i

#Union연산 각각 수행
for i in range(e):
    a,b = map(int, input().split())
    union_parent(parent, a, b)

#각 원소가 속한 집합 출력
for i in range(1, v+1):
    print(find_parent(parent, i))

#부모테이블 내용 출력
for i in range(1, v+1):
    print(parent[i])

 

기본적인 구현방법의 문제점

합집합 현산이 편향되게 이루어질 경우 찾기 (Find)함수가 비효율적으로 동작

최악의 경우(아래 예시)에서 Find 함수가 모든 노드를 다 확인하게 되어 시간복잡도는 O(V)이다 

Find 함수를 최적화하기 위한 방법으로 경로압축 (Path Compression)을 이용할 수 있다 

• Find 함수를 재귀적으로 호출한 뒤에 부모테이블 값을 바로 갱신

 

서로소 집합 알고리즘 소스코드 (경로압축) 

def find_parent(parent, x):
	## 루트노드가 아니라면, 루트노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
    	parent[x] = find_parent(parant, parant[x])
    return parent[x]
    
#두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
	#각각의 루트노드를 찾는다.
    a = find_parent(parent, a) 
    b = find_parent(parent, b)
    if a<b: #두 노드중 큰 노드의 부모를 바꿔준다.
        parent[b] = a
    else:
        parent[a] = b

#노드와 간선의 개수 입력
v,e = map(int, input().split())
parent = [0] * (v+1) #부모테이블

#초기상태 - 부모를 자기자신으로 초기화
for i in range(1,v+1):
    parent[i] = i

#Union연산 각각 수행
for i in range(e):
    a,b = map(int, input().split())
    union_parent(parent, a, b)

#각 원소가 속한 집합 출력
for i in range(1, v+1):
    print(find_parent(parent, i))

#부모테이블 내용 출력
for i in range(1, v+1):
    print(parent[i])

다른 함수는 동일하고 find_parent함수만 수정해주면 된다

 

 

서로소 집합을 활용한 사이클 판별

서로소 집합은 무방향 그래프 내에서의 사이클을 판별할때 사용할 수 있다. (방향 그래프에서는 DFS)

 

사이클 판별 알고리즘은 다음과 같다 

1. 각 간선을 하나씩 확인하여 두 노드의 루트노드를 확인한다
   1. 루트노드가 서로 다르다면 두 노드에 대하여 합집합 (union)연산을 수행
   2. 루트노드가 서로 같다면 Cycle이 발생한것
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번과정을 반복한다 

예시 

노드	1	2	3
부모노드	1	2	3

일단 모든 노드의 부모노드를 자기자신으로 설정한다

 

간선 (1,2) 확인

각 부모노드의 번호중 작은 값으로 변경

노드	1	2	3
부모노드	1	1	3

 

간선 (1,3) 확인

각 부모노드의 번호중 작은 값으로 변경

노드	1	2	3
부모노드	1	1	1

 

간선 (2,3) 확인

이미 노드2와 노드3의 루트노드는 모두 1 -> 사이클이 발생

노드	1	2	3
부모노드	1	1	1

 

서로소 집합을 이용한 사이클 판별 (경로압축 이용) 

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화히기

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parnet[i] = i

cycle = False # 사이클 발생 여부

for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    # 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
    else:
        union_parent(parent, a, b)

if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")