알고리즘-심화 알고리즘 (2)

최단 경로 알고리즘

Dijkstra 알고리즘

• 출발점에서 모든 노드로의 최단 경로를 구하는 알고리즘
• 간선에 음의 가중치가 없어야 함
• 탐욕 알고리즘과 DP를 결합한 알고리즘
• 알고리즘 시간복잡도: $𝑂(𝐸 log 𝑉)$

Dijkstra 알고리즘 예시

• 다음과 같이 노드와 간선 가중치 정보가 있을 때, A 노드에서 다른 노드들에 대한 최단 경로 구하기
  
  
  
  
  
  
  
  

최단 경로 문제 풀이

1) Dijkstra 알고리즘을 구현하세요!
전체 노드의 개수 N개가 있고, 각 노드간의 연결이 edge[i] = [출발노드, 도착노드, 가중치]로 주어져 있다고 하자.
이 때 start 노드에서부터 모든 노드에 도달하기 위한 최단거리를 구하시오.

from heapq import heappop, heappush


def solution(N, edge, start):
    dists = [float('inf') for _ in range(N + 1)]
    heap = []

    heappush(heap, (0, start))
    dists[start] = 0

    while heap:
        d, node = heappop(heap)
        for _, adj_node, w in filter(lambda x: x[0] == node, edge):
            new_dist = d + w
            if new_dist < dists[adj_node]:
                dists[adj_node] = new_dist
                heappush(heap, (new_dist, adj_node))
    
    return dists[1:]



if __name__ == '__main__':
    N = 5
    edge = [[1, 2, 2], [1, 3, 3], [2, 3, 4], [2, 4, 5], [3, 4, 6], [4, 5, 1]]
    start = 1
    sol = solution(N, edge, start)
    print(sol)

2) 당신은 네비게이션 시스템을 개발하기 위해 최단 거리를 계산하는 프로그램을 만들고 테스트하려 한다.
최단 거리를 계산하고자 하는 공간에는 총 N개의 장소가 존재한다.
a번째 장소에서 b번째 장소로 이동하는 데에 걸리는 시간 time이 edge[i] = [a, b, time]로 주어진다고 하자.
당신은 0번째 장소에 있다고 할 때, 최단 거리로 도달하는 데에 가장 오래 걸리는 장소의 인덱스를 출력하시오.
단, 정답이 여럿일 경우 더 작은 인덱스를 반환하시오.

from heapq import heappop, heappush


def solution(N, edge):
    start = 0
    dists = [float('inf') for _ in range(N)]
    heap = []

    heappush(heap, (0, start))
    dists[start] = 0

    while heap:
        d, node = heappop(heap)
        for _, adj_node, w in filter(lambda x: x[0] == node, edge):
            new_dist = d + w
            if new_dist < dists[adj_node]:
                dists[adj_node] = new_dist
                heappush(heap, (new_dist, adj_node))
    
    max_val = max(dists)
    return dists.index(max_val)
    


if __name__ == '__main__':
    N = 5
    edge = [[0, 1, 5], [0, 2, 7], [1, 3, 10], [3, 4, 8], [2, 4, 9], [4, 2, 1]]
    sol = solution(N, edge)
    print(sol)

3) N개의 국가를 연결하는 다양한 비행기편이 있다. 각 국가는 0부터 N-1의 인덱스로 표현된다.
각 비행기편은 flight[i] = {출발지 인덱스, 도착지 인덱스, 비용}으로 주어진다고 한다.
당신은 k번 이하로 비행기를 탑승하면서, a 국가에서 b 국가에 도착하기 위한 최소의 비용을 구하려고 한다.
위 프로그램을 구현하시오. 단, k번 이하의 비행편으로 a 국가에서 b 국가로 도달할 수 없는 경우 -1을 출력하시오.

from heapq import heappush, heappop


def solution(N, flight, a, b, k):
    adj_lists = [[] for _ in range(N)]
    for src, dst, price in flight:
        adj_lists[src].append((dst, price))
    
    best_cnt = [float('inf') for _ in range(N)]
    heap = []
    heappush(heap, (0, 0, a))

    while heap:
        price, count, node = heappop(heap)

        if best_cnt[node] < count:
            continue

        best_cnt[node] = count

        if count > k:
            continue

        if node == b:
            return price
        
        for adj_node, add_price in adj_lists[node]:
            heappush(heap, (price + add_price, count + 1, adj_node))

    return -1


if __name__ == '__main__':
    N = 4
    flight = [[0, 2, 1], [1, 3, 20], [1, 0, 8], [2, 3, 1], [0, 3, 3]]
    a = 1
    b = 3
    k = 2
    sol = solution(N, flight, a, b, k)
    print(sol)

최소 신장 트리

• Minimum spanning Tree(MST)
• 그래프의 모든 노드를 최소 가중치 합으로 연결한 부분 트리: 부분 트리이므로, 회로가 존재해서는 안됨(Acyclic)
  

크루스칼 메소드(Kruskal's Method)

• 모든 간선을 가중치를 기준으로 오름차순 정렬 (𝑂(𝐸 log 𝐸))
  -> 모든 간선을 정렬하는 과정때문에, 간선의 수가 적을 때 사용
• 작은 가중치의 간선부터 하나씩 선택하여 MST를 구성
  -> 이 과정에서 사이클을 형성하는 간선은 선택하지 않음
  -> 사이클 형성을 판단하는 알고리즘은 Union-Find 알고리즘 사용

크루스칼 메소드 예시

유니온-파인드(Union-Find)

• 트리 형식으로 집합을 만들고 연산하는 알고리즘
  -> 유니온 (Union): 두 집합의 합집합을 계산하는 연산
  -> 파인드 (Find): 한 원소가 속한 집합을 알아내는 연산 (트리에서 루트 노드를 찾는 연산)

• 크루스칼 방법과 유니온-파인드 알고리즘
  -> 초기에 개별 노드가 크기가 1인 집합을 이룸
  -> MST에 노드를 하나 추가할 때 마다 해당 노드를 유니온 연산
  -> 노드를 추가할 때 파인드 연산으로 같은 집합의 원소인지 확인 (사이클이 발생하는지 확인)

유니온 알고리즘

• 각 노드는 부모 노드를 parents 배열에 기록: 루트 노드는 자기 자신을 부모 노드로 가짐
• Union: 두 집합 중 하나의 루트 노드를 다른 루트 노드의 부모로 함
  

Union-By-Rank

• 유니온 이후 집합의 랭크(트리의 깊이)를 최소한으로 유지하는 방법
  -> 랭크가 더 높은 집합이 루트가 되게 함
  -> 랭크가 같을 경우 아무거나 선택하고, 랭크가 1 증가
  

파인드 알고리즘

• 해당 집합의 루트 노드를 반환, 재귀적으로 동작하여 자기 자신이 부모일 때 까지 동작
  

경로 단축(Path Compression)

• Find 과정에 참여한 모든 노드의 부모를 루트 노드로 변경: 한번 Find를 동작시키면 여러 노드의 Find가 O(1)로 동작
  

프림 메소드(Prim's method)

• 임의의 노드에서 시작하여 하나씩 노드를 연결하는 방식
• 연결된 모든 노드의 간선 중 가장 낮은 가중치의 간선을 선택 (힙으로 최적화)
• 간선의 개수가 많을 경우 크루스칼 메소드보다 유리
• 시간복잡도: 𝑂(𝐸 log 𝑉)

프림 메소드 예시

최소 신장 트리 문제 풀이

1) Kruskal's Method를 구현하세요!
전체 노드의 개수 N개가 있고, 각 노드간의 연결이 edge[i] = [출발노드, 도착노드, 가중치]로 주어져 있다고 하자.
이 때 최소 신장 트리를 구성하기 위한 가중치의 총 합을 구하시오.

from heapq import heappop, heappush

def solution(N, edge):
    rank = [1 for _ in range(N+1)]
    parent = [i for i in range(N+1)]

    def union(x, y):
        x_root = find(x)
        y_root = find(y)
        if x_root == y_root:
            return False
        
        if rank[x_root] < rank[y_root]:
            x_root, y_root = y_root, x_root
        
        parent[y_root] = x_root
        rank[x_root] += rank[y_root]
        return True
    
    def find(x):
        if parent[x] == x:
            return x
        parent[x] = find(parent[x])
        return parent[x]

    heap = []
    for a, b, w in edge:
        heappush(heap, (w, a, b))
    
    mst_weight = 0
    count = 0
    while heap:
        w, a, b = heappop(heap)
        if union(a, b):
            mst_weight += w
            count += 1
        if count == N:
            break
    
    return mst_weight


if __name__ == '__main__':
    N = 5
    edge = [[1, 2, 2], [1, 3, 3], [2, 3, 4], [2, 4, 5], [3, 4, 6], [5, 1, 1]]
    sol = solution(N, edge)
    print(sol)

2) Prim's Method를 구현하세요!
전체 노드의 개수 N개가 있고, 각 노드간의 연결이 edge[i] = [출발노드, 도착노드, 가중치]로 주어져 있다고 하자.
이 때 최소 신장 트리를 구성하기 위한 가중치의 총 합을 구하시오.

from heapq import heappop, heappush

def solution(N, edge):
    visited = [False for _ in range(N+1)]
    start = 1

    heap = []
    visited[start] = True
    for a, b, w in filter(lambda x: x[0] == start or x[1] == start, edge):
        node = a if start == b else b
        heappush(heap, (w, node))
    
    mst_weight = 0
    while heap:
        w, node = heappop(heap)

        if visited[node]:
            continue

        visited[node] = True
        mst_weight += w

        for a, b, new_w in filter(lambda x: x[0] == node or x[1] == node, edge):
            new_node = a if node == b else b
            heappush(heap, (new_w, new_node))
    
    return mst_weight


if __name__ == '__main__':
    N = 5
    edge = [[1, 2, 2], [1, 3, 3], [2, 3, 4], [2, 4, 5], [3, 4, 6], [5, 1, 1]]
    sol = solution(N, edge)
    print(sol)

3) 당신에게 2차원 평면상의 좌표 x[i]와 y[i]가 주어진다.
각 좌표에 찍혀있는 점을 서로 연결하는 데에는 두 좌표 사이의 '맨하탄 거리' 만큼의 비용이 든다.
i번째 점과 j번째 점 사이의 맨하탄 거리는 아래와 같이 정의된다.
manhattan(i, j) = |x[i] - x[j]| + |y[i] - y[j]|
이 때, 모든 점을 연결하는 데에 필요한 최소의 비용을 구하시오.

from heapq import heappush, heappop


def solution(x, y):
    N = len(x)
    start = 0

    visited = [False for _ in range(N)]
    
    heap = []
    visited[start] = True
    for i in range(N):
        if i == start:
            continue
        w = m_dist((x[start], y[start]), (x[i], y[i]))
        heappush(heap, (w, i))
    
    mst_weight = 0
    while heap:
        w, node = heappop(heap)

        if visited[node]:
            continue

        visited[node] = True
        mst_weight += w

        for i in range(N):
            if i == node:
                continue
            w = m_dist((x[node], y[node]), (x[i], y[i]))
            heappush(heap, (w, i))
            
    return mst_weight

def m_dist(pt1, pt2):
    return abs(pt1[0] - pt2[0]) + abs(pt1[1] - pt2[1])


if __name__ == '__main__':
    x = [0, 0, 3, 3, 6]
    y = [0, 3, 1, 4, 3]
    sol = solution(x, y)
    print(sol)

from heapq import heappush, heappop

def solution(x, y):
    n = len(x)
    root = list(range(n))
    rank = [1]*n

    def union(i, j):
        i_root = find(i)
        j_root = find(j)
        if i_root != j_root:
            if rank[i_root] >= rank[j_root]:
                root[j_root] = i_root
                rank[i_root] += rank[j_root]
            else:
                root[i_root] = j_root
                rank[j_root] += rank[i_root]
        
    def find(i):
        if i != root[i]:
            i = find(root[i])
        return root[i]
    
    def manhattan(i, j):
        return abs(x[i] - x[j]) + abs(y[i] - y[j])
        
    heap = []
    for i in range(n-1):
        for j in range(i+1, n):
            d = manhattan(i, j)
            heappush(heap, (d, i, j))
    
    total_dist = 0
    edges = []
    while len(edges) < n - 1:
        d, i, j = heappop(heap)
        if find(i) == find(j):
            continue
        union(i, j)
        edges.append((d, i, j))
        total_dist += d
    
    return total_dist

4) 당신은 좀비 바이러스 치료제를 단 하나 가지고 있다.
이번에 매우 전염성이 높은 좀비 바이러스가 퍼져, 긴급히 방역이 필요한 상황이다.
총 N명의 인원이 관리 대상으로, i번째 인원과 j번째 인원이 서로 가까이 있어 감염시킬 수 있는 경우 graph[i][j]가 1로 주어진다.
서로 가까이 있는 인원 중에 한 명이라도 감염된 인원이 있다면, 결국 모두 서로를 감염시키게 된다.
현재 좀비 바이러스에 감염된 인원은 infected 배열에 주어진다.
당신은 치료제가 단 하나 있기 때문에, infected 의 인원 중 한 명을 치료할 수 있다.
이 때, 어떤 인원을 치료해야 좀비 바이러스에 감염되는 인원을 최소화할 수 있는지 해당 인원의 인덱스를 출력하시오.
단, 정답이 여럿인 경우 더 작은 인덱스를 출력하시오.

def solution(N, graph, infected):
    rank = [1 for _ in range(N)]
    parent = [i for i in range(N)]

    def union(x, y):
        x_root = find(x)
        y_root = find(y)
        if x_root == y_root:
            return False
        
        if rank[x_root] < rank[y_root]:
            x_root, y_root = y_root, x_root
        
        parent[y_root] = x_root
        rank[x_root] += rank[y_root]
        return True
    
    def find(x):
        if parent[x] == x:
            return x
        parent[x] = find(parent[x])
        return parent[x]
    
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1:
                union(i, j)
    
    infected.sort()

    comps = dict()
    for i in infected:
        root = find(i)
        if root not in comps:
            comps[root] = []
        comps[root].append(i)
    
    max_ind = -1
    max_size = -1
    for i in infected:
        root = find(i)
        current_size = rank[root]

        if len(comps[root]) > 1:
            current_size = 0
        if current_size > max_size:
            max_ind = i
            max_size = current_size
    
    return max_ind


if __name__ == '__main__':
    N = 3
    graph = [[1, 1, 0],
            [1, 1, 0],
            [0, 0, 1]]
    infected = [0, 2]
    sol = solution(N, graph, infected)
    print(sol)

이 글은 제로베이스 데이터 취업 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다