[코테, 알고리즘] 프로그래머스 고득점 Kit - 그래프 (2)

김재연·2023년 7월 23일
0
post-thumbnail

📌 그래프는 자료구조편알고리즘편, 알고리즘-최단경로편, 코드편 총 4편으로 나누어서 작성

본격적으로 정리하기 전에 그래프 알고리즘에는 어떤게 있나, 하고 찾아봤더니 n년전에 학교에서 배우고 기억 저편으로 넘어갔던 알고리즘들의 어렴풋한 이름들이 우르르 나오면서 뭐가 뭔지 모르겠어서 분류를 해봤다.

  1. 그래프 내의 모든 정점을 순회하는 알고리즘
    • DFS (완료)
    • BFS (완료)
  2. 최소 신장 트리를 만드는 알고리즘
    • 크루스칼 알고리즘
    • 프림 알고리즘
  3. 그래프 상에서 최단경로를 탐색하는 알고리즘
    • 다익스트라 알고리즘
    • 벨만 포드 알고리즘
    • 플로이드 워셜 알고리즘
  4. 작업 사이에 특정 의존(순서)관계가 있을때 이를 정렬하는 알고리즘
    • 위상정렬 알고리즘

(3번 최단경로 알고리즘은 나중에 따로 주제를 빼서 작성할 예정)

우선 시작하기 전에 그래프 알고리즘에서 중요한 개념인 서로소 집합최소신장트리에 대해 알아보자.


1. 서로소 집합 (Disjoint Set)

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

(1) 합치기 연산 과정

서로소 집합 자료구조는 기본적으로 트리 자료구조를 사용한다.

  1. union 연산을 확인하고, 합치려는 두 노드 A, B를 확인한다.
  2. A의 루트노드 A'B의 루트노드 B'를 찾는다.
  3. A'B'의 부모 노드로 설정한다.
  4. 모든 union 연산을 처리할 때까지 1~3번 과정을 반복한다.

cf) 부모노드를 저장하는 테이블의 초기값은 자기 자신이다.




(2) 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

💡 a와 b를 합칠 때 a의 부모를 b로(b의 부모를 a로) 바꾸는게 아니라, a의 부모의 부모를 b의 부모(b의 부모의 부모를 a의 부모로) 바꾸는 것에 주의한다.


(3) 서로소 집합으로 사이클 판별하기

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

  1. 각 간선을 하나씩 확인하며 두 노드의 루트노드를 확인한다. (find)
  2. 루트노드가 서로 다르면 두 노드에 대하여 합집합 연산을 수행한다. (union)
  3. 루트노드가 서로 같다면 사이클이 발생한 것이다.
  4. 그래프에 포함되어 있는 모든 간선에 대해 1~3번 과정을 반복한다.
for e in {모든 간선} :
    a, b = {간선 e에 포함된 두 노드}
    if find_parent(parent, a) == find_parent(parent, b):
        {사이클 발생}
        break
    else:
        union_parent(parent, a, b)

2. 최소신장트리 (MST)

(1) 신장트리 (Spanning Tree)

  • 그래프 내의 모든 정점을 포함하는 최소 연결 부분 그래프 (간선의 수가 가장 적게, 하지만 정점은 모두 연결된 부분 그래프)
  • 신장트리는 그래프에 있는 N개의 정점을 N-1개의 간선으로 연결한다.
  • 하나의 그래프에 많은 신장트리가 존재할 수 있다.
  • 사이클을 포함할 수 없다.

(2) 최소신장트리 (Minimum Spanning Tree)

  • 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리
  • 다만, 각 간선의 가중치가 동일하지 않을때 가장 적은 간선을 사용한다고 최소비용이 얻어지는 것은 아니다.
  • 그럼 어떻게 구하느냐? 여기서 필요한게 바로 크루스칼 알고리즘프림 알고리즘이다.

3. 크루스칼 알고리즘 (Kruskal Algorithm)

(1) 동작과정

  1. 간선 데이터를 가중치에 따라 오름차순으로 정렬한다.
  2. 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인한다.
  3. 사이클 발생 X -> 현재 간선을 최소신장트리에 포함시킨다.
  4. 사이클 발생 O -> 현재 간선을 최소신장트리에 포함시키지 않는다.
  5. 모든 간선에 대해서 2~4번 과정을 반복한다.


(2) 구현하기

edges = [가중치에 따라 오름차순 정렬된 모든 간선]
parent = [부모 테이블]
total_cost = 0 # 최소신장트리의 가중치

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
    
for i in range(간선개수):
	cost, a, b = edges[i]
    if find_parent(parent, a) != find_parent(parent, b):
    	union_parent(parent, a, b)
        total_cost += cost
        # 사이클이 발생하지 않았으므로 이번 edges[i]는 최소신장트리에 포함됨

(3) 특징

  • 모든 간선에 대해 정렬한 뒤 거리가 가장 짧은 간선부터 집합에 포함시키기 때문에 그리디 알고리즘으로 분류된다.
  • 사이클 발생여부는 위에서 설명한 서로소집합의 find_parentunion_parent 함수를 이용해서 확인할 수 있다.
  • 음수 가중치가 있을 때도 올바르게 작동한다.

4. 프림 알고리즘 (Prim Algorithm)

  1. 시작 정점을 골라서 최소신장트리에 추가한다.
  2. 정점과 이어진 간선을 살핀다. 간선과 이어진 다음 정점이 최소신장트리에 있지 않다면 이 정점과 간선을 최소힙에 추가한다.
  3. 최소힙에서 꺼낸 정점이 최소신장트리에 포함되어 있지 않다면 최소신장트리에 추가하고 2번 과정을 다시 진행한다. 만약 꺼낸 정점이 최소신장트리에 이미 포함되어있다면 그냥 넘어간다.
  4. 최소힙이 빌때까지 3번 과정을 반복한다.

코테에서 많이 쓰는 알고리즘은 아닌거 같아서 구현은 생략 (절대 귀찮아서 안하는거 아님)


5. 위상정렬 (Topological Sort)

(1) 개념

  • 정렬 알고리즘의 일종
  • 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘
  • 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 방법
  • ex) 자료구조, 알고리즘, 운영체제 3과목이 있을때, 올바른 수강순서는 자료구조->알고리즘->운영체제이다. 자료구조->운영체제->알고리즘은 올바르지 않은 순서다.

(2) 동작과정

위상정렬은 큐를 이용하여 구현한다.

  1. 진입차수가 0인 노드를 큐에 넣는다.
  2. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
  3. 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다.
  4. 큐가 빌때까지 2~3번 과정을 반복한다.

각 노드가 큐에 들어온 순서가 위상정렬을 수행한 결과다.


(3) 구현하기

v = {노드개수}
indegree = [모든 노드에 대한 진입차수]

def topology_sort():
    result = []
    q = deque()

    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)

        for g in graph[now]:
            indegree[g] -= 1
            if indegree[g] == 0:
                q.append(g)
                
	return result
profile
일기장같은 공부기록📝

0개의 댓글