그래프 (Graph)

그래프(Graph)는 노드(Node)와 간선(Edge)으로 이루어진 자료구조로, 다양한 현실 세계의 관계를 모델링하는 데 사용된다.

Baekjoon - Graph Theory

Baekjoon - Graph Traversal

그래프의 주요 주제 및 개념은 다음과 같다.

Union-Find

유니온 파인드(Union-Find)는 여러 개의 집합을 효율적으로 관리하고 조작하기 위한 자료구조이다. 주로 상호 배타적인(disjoint) 집합들을 다루는 데 사용되며, 서로 중복되지 않는 원소들로 구성된 집합들의 관계를 다루는 것을 목적으로 한다. 유니온 파인드는 또한 "디스조인트 셋(Disjoint Set)" 또는 "합집합 찾기(Union Find)" 자료구조로도 불린다.

Baekjoon - Disjoint Set

---

주요한 두 가지 연산이 유니온 파인드 자료구조에서 지원되며 각 호출의 시간복잡도는 O(log n)이다:

1. Union(합집합) 연산: 두 개의 집합을 하나로 합치는 연산이다. 두 원소가 속한 집합을 찾아서 하나의 집합으로 합친다.
2. Find(찾기) 연산: 주어진 원소가 어떤 집합에 속해 있는지를 찾는 연산이다. 두 원소가 같은 집합에 속해 있는지 여부를 판단할 때 사용된다.

def find(parents, n):

    if parents[n] != n:
        parents[n] = find(parents, parents[n])

    return parents[n]

def union(parents, u, v):

    u = find(parents, u)
    v = find(parents, v)

    if u < v:
        parents[v] = u
    else:
        parents[u] = v

Floyd-Warshall

플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프 내 모든 정점 사이의 최단 경로를 찾는 데 사용되는 알고리즘이다. 이 알고리즘은 음수 가중치를 갖는 간선이 있을 때에도 작동하며, 다익스트라 알고리즘과는 다르게 모든 정점 사이의 최단 경로를 찾을 수 있다. 이 알고리즘은 세 개의 반복문을 사용하여 모든 정점 사이의 최단 경로를 구하며, 시간 복잡도는 일반적으로 O(V^3)이다. 여기서 V는 정점의 수를 나타낸다.

Baekjoon - Floyd–warshall

---

알고리즘은 다음과 같다:

1. 초기화: 먼저, 각 정점 사이의 거리나 가중치를 나타내는 인접 행렬을 설정한다. 인접 행렬은 간선의 가중치로 초기화되며, 두 정점 사이에 직접적인 간선이 없는 경우는 무한대 또는 충분히 큰 값으로 초기화된다.
2. 반복적인 최단 경로 찾기: 플로이드-워셜 알고리즘은 세 개의 반복문을 사용하여 모든 정점을 거쳐가는 경로를 고려한다. 각 단계에서는 현재까지 발견된 최단 경로를 사용하여 더 짧은 경로를 찾아 업데이트한다. - 외부 반복문은 거쳐가는 정점을 순회한다. - 중간 반복문은 출발하는 정점을 순회한다. - 내부 반복문은 도착하는 정점을 순회하며 최단 경로를 업데이트한다.
3. 최단 경로 업데이트: 알고리즘이 모든 정점을 거쳐가는 경우를 고려하여 최단 경로를 업데이트한다. 각 정점을 거쳐가는 경우를 검사하면서 해당 경로가 더 짧은 경로라면 최단 경로를 업데이트한다.
4. 결과 출력: 알고리즘이 완료된 후에는 최종적으로 모든 정점 사이의 최단 경로가 업데이트된 인접 행렬을 통해 얻을 수 있다.

# node 개수
n = 4

# [start_node, end_node, weight] 정보를 넣은 edge 리스트
edges = [[1, 2, 4], [1, 4, 6], [2, 1, 3],
         [2, 3, 7], [3, 1, 5], [3, 4, 4],
         [4, 3, 2]]

def floyd_warshall(n, edges):

    # 초기화
    INF = int(1e9)
    graph = [[INF] * n for _ in range(n)]

    for a in range(n):
        for b in range(n):
            if a == b:
                graph[a][b] = 0

    for i in range(len(edges)):
        a, b, c = edges[i]
        graph[a-1][b-1] = c

    # 플로이드 워셜 알고리즘을 수행
    for k in range(n):
        for a in range(n):
            for b in range(n):
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

    return graph

result = floyd_warshall(n, edges) # [[0, 4, 8, 6], [3, 0, 7, 9], [5, 9, 0, 4], [7, 11, 2, 0]]

Bellman-Ford

벨만-포드(Bellman-Ford) 알고리즘은 그래프에서 음의 가중치가 있는 간선을 포함하는 경우에도 단일 출발점에서 모든 정점으로의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 음수 가중치의 간선이 있을 때에도 작동하며, 음수 사이클이 없는 경우에는 정확한 최단 경로를 찾을 수 있다. 시간 복잡도는 일반적으로 O(V*E)이다.

Baekjoon - Bellman–ford

---

알고리즘의 작동 방식은 다음과 같다:

1. 초기화: 출발 노드를 제외한 모든 노드들의 최단 거리를 무한대로 초기화하고, 출발 노드의 최단 거리를 0으로 설정한다.
2. 간선을 반복적으로 확인: 모든 간선을 순회하면서 각 간선의 시작 노드까지의 최단 거리에 해당 간선의 가중치를 더했을 때, 도착 노드까지의 현재까지의 최단 거리보다 더 짧은 경로를 발견하면 최단 거리를 업데이트한다.
3. 반복적인 갱신: 간선을 모두 순회하며 최단 거리를 업데이트하는 과정을 충분한 반복 횟수만큼 수행한다. 일반적으로 정점의 개수인 V번의 반복을 수행한다.
4. 음수 사이클 탐지: 추가로 V번째 반복을 수행하여 최단 거리가 더 줄어드는 경우가 있는지 확인한다. 만약 V번째 반복에서도 최단 거리가 갱신된다면, 음수 사이클이 존재한다는 것을 의미한다.

# node 개수
n = 5

# [start_node, end_node, weight] 정보를 넣은 edge 리스트
edges = [[1, 2, -4], [1, 3, 5], [1, 4, 2],
         [1, 5, 3], [2, 4, -1], [3, 4, -7],
         [4, 5, 6], [5, 4, -4]]

def bellman_ford(start, n, edges):

    INF = int(1e9)
    distance = [INF] * (n + 1)
    distance[start] = 0

    for i in range(n):
        for j in range(len(edges)):
            cur_node, next_node, cost = edges[j]

            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if distance[cur_node] != INF and distance[cur_node] + cost < distance[next_node]:
                distance[next_node] = distance[cur_node] + cost

                # negative cycle 존재
                if i == n - 1:
                    return []

    return distance[1:]

result = bellman_ford(1, n, edges) # [0, -4, 5, -5, 1]

Topological Sort

위상 정렬(Topological Sort)은 방향 그래프에서 작업이나 이벤트들 간의 선후 관계에 따라 순서를 정하는 알고리즘이다. 이를 통해 사이클이 없는 그래프에서 각 노드들의 순서를 결정할 수 있다. 만약 사이클이 존재한다면 위상 정렬을 할 수 없다. 알고리즘의 특징 중 하나는 여러 가지 순서가 가능한 경우가 있다는 점이다. 시간 복잡도는 보통 노드의 수를 V, 간선의 수를 E라고 할 때 O(V + E)로 표현된다.

Baekjoon - Topological Sorting

---

알고리즘의 작동 방식은 다음과 같다:

1. 진입 차수 계산:각 노드의 진입 차수(입력 차수)를 계산한다. 진입 차수란 특정 노드로 들어오는 간선의 수를 말한다.
2. 진입 차수가 0인 노드 탐색:진입 차수가 0인 모든 노드를 탐색하여 이들을 시작 노드로 선택한다. 진입 차수가 0인 노드는 그래프에서 선행 작업이 없는 노드이다.
3. 선행 작업 제거: 선택한 노드를 방문하고, 이 노드와 연결된 간선을 제거한다. 이로 인해 연결된 노드들의 진입 차수가 감소한다.
4. 반복: 진입 차수가 0이 된 새로운 노드를 선택하고 위의 과정을 반복하다. 이를 모든 노드가 방문될 때까지 수행한다.

from collections import deque

def topological_sort(graph):
    # 진입 차수 계산
    indegree = {}
    for node in graph:
        indegree[node] = 0

    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] += 1

    # 진입 차수가 0인 노드 찾기
    zero_indegree = deque([node for node, num in indegree.items() if num == 0])
    result = []

    # 위상 정렬 수행
    while zero_indegree:
        node = zero_indegree.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                zero_indegree.append(neighbor)

    # 사이클이 존재하는 경우
    if len(result) != len(graph):
        return None

    return result

graph = {
    'A': ['B', 'C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['D', 'F'],
    'F': []
}

result = topological_sort(graph) # ['A', 'B', 'C', 'E', 'D', 'F']