[ 이것이 코딩테스트다 ] 28일차

✏️ 서론

오늘은 마지막 챕터인 기타 그래프 이론에 대해 알아보자.

지금까지 코딩 테스트에서 출제 비중이 높은 알고리즘 유형들을 다뤄보았다. 기타 그래프 이론은 지금까지 다루지 않은 그래프 알고리즘을 추가로 다뤄보자. 이전에 배웠던 DFS / BFS와 최단 경로에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다.

본론으로 들어가기 앞서, 그래프에 대해 복습해보자.
그래프(graph)란, 노드(node)와 노드 사이에 연결된 간선(edge)의 정보를 가지고 있는 자료구조를 의미한다.

만약, 알고리즘 문제를 풀다가 서로 다른 개체(혹은 객체(object))가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다.

예를들어, 여러 개의 도시가 연결되어 있다.와 같은 내용이 등장하면 그래프 알고리즘을 의심해보자.

더불어 그래프 자료구조 중에서 트리(tree) 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억하자.

참고로 트리는 전통적인 수학에서는 무방향 그래프로 간주되지만, 컴퓨터공학 분야에서는 보통 방향 그래프로 간주된다.

구분	그래프(graph)	트리(tree)
방향성	방향 그래프 혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드 없음	루트 노드 존재
노드간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

또한, 그래프의 구현 방법은 2가지 방식이 존재하는데, 다음과 같다.

1. 인접행렬(adjacency_matrix): 2차원 배열을 사용하는 방식
2. 인접리스트(adjacency_list): 리스트를 사용하는 방식

또, 노드의 개수가 V, 간선의 개수가 E인 그래프를 가정해보면 다음의 표를 떠올릴 수 있다.

구분	인접행렬	인접리스트
메모리 공간	O(V^2)	O(E)
간선의 비용	O(1)	O(V)
알고리즘	floyd_warshall	heap_dijkstra
노드의 개수	V^2개	V개

여기서 알아두어야 할점은 어떤 문제를 만나든 메모리와 시간을 염두에 두고 알고리즘을 선택해서 구현해야한다.

예를 들어, 최단 경로를 찾아야하는 문제가 나올때 노드의 개수가 적다면 floyd_warshall을 사용하고 노드와 간선의 개수가 모두 많으면 heap_dijkstra 알고리즘을 이용하면 유리하게 문제를 풀 수 있다.

---

✏️ 본론

📍 서로소 집합(disjoint_sets)

수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
예를 들면, 집합 {1, 2}와 {3, 4}는 서로소 관계이다.
반면에, 집합 {1, 2}와 {2, 3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다.

서로소 집합 자료구조는 union-find(합치기 - 찾기) 자료구조라고도 불린다.
또한, 자료구조를 구현할때는 트리 자료구조를 이용하여 집합을 표현하는데, 알고리즘은 다음과 같다.

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

기존 시간복잡도는 O(V)였으나, 개선된 알고리즘을 사용하면 시간복잡도는 O(V+M(1+logV))정도로 줄어든다.

'''
6 4
1 4
2 3
2 4
5 6
'''

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    else:
        return parent[x]

def union_parent(parent, a, b):
    a = find_parent(a)
    b = find_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_parents(parent, i), end=' ')

print()

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

👉🏽 각 원소가 속한 집합: 1 1 1 1 5 5 
부모원소의 집합: 1 1 2 1 5 5 

---

📍 경로 압축기법 코드

# 기존 코드는 else return 값이 x였음.
def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    else:
        return parent[x]

---

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

서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할수 있다는 특징이 있다.
참고로 방향 그래프에서의 사이클 여부는 DFS통해 판별할 수 있으며, 개인적으로 공부하도록 하자.

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

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다

• 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
• 루트 노드가 서로 같다면 사이클(cycle)이 발생한 것이다.

2. 그래프에 포함되어 있는 모든 간선에 대하여 1번과정을 반복한다.

'''
3 3
1 2
1 3
2 3
'''

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    else:
        return parent[x]

def union_parent(parent, a, b):
    a = find_parent(a)
    b = find_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

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:
    print('cycle이 발생했습니다.!')
else:
    print('cycle이 발생하지 않았습니다.!')

👉🏽 cycle이 발생하지 않았습니다.!

---

✏️ 결론

이렇게 해서 서로소 집합에 대해서 배워봤다.
내일과 내일 모레 2일에 걸쳐서는 크루스칼 알고리즘, 위상정렬을 배울텐데, 까먹지 않도록 계속해서 코드를 작성하는 연습을 해야겠다.