이것이 코딩 테스트다 - Chapter10 그래프 이론 정리

"그래프 이론"이란

코딩 테스트에서 자주 등장하는 기타 그래프 이론 공부하기

 

이론의 마지막 챕터로 그래프 이론에 대해 정리한다.

 

1. 서로소 집합

공통 원소가 없는 두 집합을 의미하며, 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

즉, 겹치지 않게 집합을 나누는 자료구조이다.

 

이때 두가지 연산이 사용된다.

1) union연산 : 두 원소를 하나의 집합으로 묶는다.

2) find연산 : 해당 원소가 어떤집합에 속하는지를 찾아준다.

 

이 연산을 통해 서로소 집합을 구현할 수 있다.

이때, 트리 자료구조를 사용하여 동일한 루트로 묶는것으로 집합을 나누게 된다.

1) union 연산 : 두 원소의 루트 중 작은원소를 루트로 삼아 묶는다.

2) find연산 : 해당 원소의 루트 원소를 반환한다.

이렇게 볼 수 있겠다.

 

이때, 주의할 점은 union 연산시 루트를 찾는 find 연산이 사용되며 재귀적으로 이루어진다는 점이다.

해당 코드를 보고 간단하게 설명하겠다

#find 함수, 계속 갱신하며 루트값을 찾는다
def find_parent(parent, x) :
  if parent[x] != x :
    parent[x] = find_parent(parent, parent[x])
  return parent[x]

#union 함수, 두 노드의 루트값 중 작은값을 루트로 묶는다
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

#간선 입력
for i in range(e) :
  a, b = map(int, input().split())
  union_parent(parent, a, b)

#각 노드의 루트를 구하여 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v+1) :
  print(find_parent(parent, i), end=' ')

print()

#부모테이블 저장된 노드 출력
print('부모 테이블: ', end = '')
for i in range(1, v+1) :
  print(parent[i], end = ' ')

6개의 노드이며 간선 4개를 추가하는 경우를 보겠다.

 

union 1, 4 : 루트값 : [1, 2, 3, 1, 5, 6]

union 2, 3 : 루트값 : [1, 2, 2, 1, 5, 6]

union 2, 4 : 루트값 : [1, 1, 2, 1, 5, 6]

union 5, 6 : 루트값 : [1, 1, 2, 1, 5, 5]

하지만 재귀를 통해 3의 루트값이 2지만, 2의 루트값이 1이므로 

최종적으로 루트값은 [1, 1, 1, 1, 5, 5] 이 되어 1, 5의 두가지 집합으로 나뉘게 된다.

 

시간복잡도 : O(V + M(1+log2 V) V:노드수, M:find연산수

 

 

 

 

2. 사이클 판별

서로소 집합 알고리즘을 활용하여 입력된 간선의 시작, 끝점의 루트가 같은경우 사이클 발생이다.

즉, 사이클 발생여부는 간선추가시 시작, 종료점의 find연산값 비교를 통해 바로 알 수 있다.

 

단, 무향 그래프에서만 적용된다는 점이 중요하다.

def find_parent(parent, x) :
  if parent[x] != x :
    parent[x] = 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

#사이클 여부 저장
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
  else :
    union_parent(parent, a, b)

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

3개의 노드이며 간선 3개를 추가하는 경우를 보겠다.

 

간선 1, 2 : [1, 2, 3] 즉 1 != 2 이므로 union 1, 2 실행 -> [1, 1, 3]

간선 1, 3 : [1, 1, 3] 즉 1 != 3 이므로 union 1, 3 실행 -> [1, 1, 1]

간선 2, 3 : [1, 1, 1] 즉 1 == 1 이므로 사이클이 발생한 경우이다.

 

 

 

3. 신장 트리 - 크루스칼 알고리즘

신장트리란 모든 노드를 포함하며 사이클이 존재하지 않는 부분 그래프이다.

이를 구하는 알고리즘이 크루스칼 알고리즘이다.

 

이때, 사이클 없이 모든 노드를 연결하는 간선을 선택하는 기준이 보통 최소비용의 간선을 통해 생성된다.

즉, 비용을 기준으로 간선을 정렬하여 가장 적은값의 간선부터 차례로 사이클 발생 여부를 확인하며 연결한다.

 

따라서 서로소 집합 알고리즘, 사이클 판별 알고리즘을 활용하여 구현된 크루스칼 알고리즘은 이렇다.

def find_parent(parent, x) :
  if parent[x] != x :
    parent[x] = 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

v, e = map(int, input().split())
parent = [0]*(v+1)
#간선 테이블, 합산 비용
edges = []
result = 0

for i in range(1, v+1) :
  parent[i] = i

for i in range(e) :
  a, b, cost = map(int, input().split())
  #비용, 시작점, 끝점 순서로 간선 저장
  edges.append((cost, a, b))

edges.sort()

#간선이 사이클이 아닌 경우 union으로 합친다
for edge in edges :
  cost, a, b = edge
  if find_parent(parent, a) != find_parent(parent, b) :
    union_parent(parent, a, b)
    result += cost

print(result)

여기서 특이점은 리스트.sort()시 0번째 인덱스 값을 기준으로 정렬되기 때문에

0번째에 간선비용이 들어가야 한다는 점이다.

그렇게 for문을 통해 사이클 발생하지 않을경우 union 시키며 전체 cost값에 더해가면 되겠다.

또한, 결과적으로 연결된 총 간선수는 노드수 N-1개가 된다.

 

7개의 노드와 9개의 간선이 입력되는 경우를 보겠다.

 

비용 순으로 정렬된 9개의 간선은 이와같다.

(7 : 3,4), (13 : 4,7), (23 : 4,6), (25 : 6,7), (29 : 1,2), (34 : 2,6), (35 : 2,3), (53 : 5,6), (75 : 1,5)

1. 간선 3,4 확인 : [1, 2, 3, 4, 5, 6, 7] 즉 3 != 4 따라서 [1, 2 ,3 ,3 ,5 ,6 ,7], 비용합 = 7

2. 간선 4,7 확인 : [1, 2, 3 ,3 ,5 ,6 ,7] 즉 3 != 7 따라서 [1, 2, 3 ,3 ,5 ,6 ,3], 비용합 = 20

3. 간선 4,6 확인 : [1, 2, 3 ,3 ,5 ,6 ,3] 즉 3 != 6 따라서 [1, 2 ,3 ,3 ,5 ,3 ,3], 비용합 = 43

4. 간선 6,7 확인 : [1, 2 ,3 ,3 ,5 ,3 ,3] 여기서 3 == 3 따라서 사이클 발생하므로 넘어간다

5. 간선 1,2 확인 : [1, 2 ,3 ,3 ,5 ,3 ,3] 즉 1 != 2 따라서 [1, 1 ,3 ,3 ,5 ,3 ,3], 비용합 = 72

6. 간선 2,6 확인 : [1, 1 ,3 ,3 ,5 ,3 ,3] 즉 1 != 3 따라서 [1, 1 ,3 ,3 ,5 ,1 ,3], 비용합 = 106

여기서 재귀적으로 6의 루트인 3이 1로 변경됨에 따라 [1, 1, 1, 1, 5 ,1 ,1] 로 변경된다

7. 간선 2,3 확인 : [1, 1, 1, 1, 5 ,1 ,1] 여기서 1 == 1 따라서 사이클이 발생하므로 넘어간다

8. 간선 5,6 확인 : [1, 1, 1, 1, 5 ,1 ,1] 즉 1 != 5 따라서 [1, 1, 1, 1, 1, 1, 1], 비용합 = 159

9. 간선 1,5 확인 : [1, 1, 1, 1, 1, 1, 1] 여기서 1 == 1 따라서 사이클이 발생하므로 넘어간다

 

결과적으로 6개의 간선이 연결되어 최소비용 159를 구할 수 있다.

코드는 간단한 수정으로 구현되지만, 내부적으로 이뤄지는 원리 이해를 잘 해야한다.

 

시간복잡도 : O(E log E) E:간선의 개수

 

 

 

4. 위상 정렬

방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 알고리즘.

즉, 선후 관계를 지키는 전체 순서를 찾을 수 있다.

 

이를 구하려면 진입차수 개념이 필요하다.

진입차수는 특정 노드로 도착하는 간선의 개수이다.

이를 통해 시작노드는 진입차수가 0개이다. 이 노드를 시작점으로 큐에 넣어 시작한다.

 

큐에서 노드를 꺼내어 해당 노드에 연결된 간선을 삭제하며 진입차수가 0개가 되는 노드를 큐에 넣는식으로 구현된다.

이때 주의점은 간선이 삭제되어 두가지 이상의 노드가 0이 되는 경우는 노드값이 작은 노드를 먼저 방문하는 식으로 구현된다.

from collections import deque

#위상정렬함수
def topology_sort(graph, indegree) :
  result = []
  q = deque()

  #입력간선수가 0인 시작점을 큐에 넣는다
  for i in range(1, v+1) :
    if indegree[i] == 0 :
      q.append(i)
  
  #큐기 빌동안 하나씩 빼며 반복
  while q :
    now = q.popleft()
    result.append(now)
    #인접 간선을 없앤다
    for i in graph[now] :
      indegree[i] -= 1
      
      #만약 간선수가 0이면 큐에 넣는다
      if indegree[i] == 0 :
        q.append(i)
  
  for i in result :
    print(i, end = " ")

#노드, 간선수 입력
v, e = map(int, input().split())
#입력간선값 리스트 0으로 초기화
indegree = [0]*(v+1)
#인접리스트 초기화
graph = [[] for i in range(v+1)]

#간선을 입력받아 넣으며, b의 입력간선수를 증가한다
for i in range(e) :
  a, b = map(int, input().split())
  graph[a].append(b)
  indegree[b] += 1

topology_sort(graph, indegree)

7가지 노드와 8가지 간선이 입력되는 경우를 보겠다.

 

간선입력 : (1,2), (1,5), (2,3), (2,6), (3,4), (4,7), (5,6), (6,4)

-> indegree수 : [0, 1, 1, 2, 1, 2, 1] 이므로 시작노드가 1이 되겠다. 큐 = [1]

1 출력, (1,2), (1,5) 삭제 : [0, 0, 1, 2, 0, 2, 1] 이므로 2, 5 노드가 추가된다. 큐 = [2, 5]

2 출력, (2,3), (2,6) 삭제 : [0, 0, 0, 2, 0, 1, 1] 이므로 3 노드가 추가된다. 큐 = [5, 3]

5 출력, (5,6) 삭제 : [0, 0, 0, 2, 0, 0, 1] 이므로 6 노드가 추가된다. 큐 = [3, 6]

3 출력, (3,4) 삭제 : [0, 0, 0, 1, 0, 0, 1] 이므로 다음으로 넘어간다.

6 출력, (6,4) 삭제 : [0, 0, 0, 0, 0, 0, 1] 이므로 4 노드가 추가된다. 큐 = [4]

4 출력, (4,7) 삭제 : [0, 0, 0, 0, 0, 0, 0] 이므로 7 노드가 추가된다. 큐 = [7]

7 출력, 삭제될 간선이 없으므로 종료된다.

 

따라서 1, 2, 5, 3, 6, 4, 7 순으로 출력된다.

 

시간복잡도 : O(V+E) V:노드수, E:간선수

 

 

 

 

 

이렇게 모든 이론에 대해 알아보았다.

정리된대로 차근차근 코딩테스트 문제를 잘 풀어나가면 되겠다.

 

깃허브 - github.com/CodingTestStudy/FreeDeveloper_Cote/tree/main/10.%20그래프%20이론

CodingTestStudy/FreeDeveloper_Cote