알고리즘 - 최소신장트리(MST)

오늘 부터는 날짜가 아니라 주제를 제목으로 하려고 한다. 왜냐하면 날짜가 제목이어서 헷갈리거나 생각이 잘 안나는 내용들을 찾기가 좀 어려웠다...

 

오늘 배운건 최소신장 트리이다. 

• 최소 신장 트리(Minimum Spanning Tree, MST)란?
  • 최소 스패닝 트리 라고도 많이 불린다.
  • 주어진 그래프의 모든 정점을 지나면서, 간선의 가중치 합이 최소가 되는 트리
    • 그래프의 모든 정점을 포함하고
    • 그래프의 일부 간선을 포함하며
    • 사이클이 없는 (트리의 특징)
    • 위 특징을 가진 서브 그래프 중 간선의 가중치 합이 최소인 트리
  • 원본 그래프 간선에 가중치가 부여되어 있음
  • 간선의 방향 여부에 따라 구하는 방법이 달라짐
    • 코딩테스트에서는 간선의 방향이 없는, 무방향 그래프에 대해서만 나온다
  • 정점이 n 개인 그래프의 최소 신장 트리는, n - 1 개의 간선을 가져야 한다 (트리의 특징)

주요 알고리즘

• 프림 (Prim’s Algorithm)
• 작동 순서
  
  1. 임의의 정점을 시작으로 선택한다.
  2. 해당 정점과 연결된 간선을 탐색 대상에 추가한다.
  3. 탐색 대상에서 가장 가중치가 낮은 간선을 뽑는다. 간선의 끝 점이 아직 방문하지 않았다면, 그 간선을 추가한다. 방문했다면, 방문하지 않은 간선이 나올 때까지 간선을 뽑는다.
  4. 새로 추가된 정점과 연결된 간선을 탐색 대상에 추가한다.
  5. 3 ~ 4번 과정을 (전체 정점 - 1) 개의 간선이 트리에 추가될 때까지 반복한다.

 

• 크루스칼 (Kruskal’s Algorithm)
  • 작동 순서
    
    1. 모든 간선들을 가중치에 대해 오름차순으로 정렬한다.
    2. 앞에서부터, 간선을 트리에 추가했을 때, 사이클이 생기지 않는다면 그 간선을 트리에 추가한다.
       • 사이클이 생긴다면 그대로 넘어간다 (간선을 트리에 추가하지 않는다)
    3. 2번 과정을 (전체 정점 - 1) 개의 간선이 트리에 추가될 때까지 반복한다.
    ❓ 사이클이 생겼는지 어떻게 알 수 있나요? 매번 그래프 탐색을 해야 하나요?→ 매 간선을 추가할 때마다 그래프 탐색을 하는 건 비효율적이라, 새로운 알고리즘을 사용해야 합니다.

분리 집합 (Union-Find / Disjoint-Set)

그래프가 유동적으로 변할 때(간선이 추가/삭제 될 때), 점들 간의 연결 여부를 빠르게 확인할 수 있어, 크루스칼 알고리즘 구현 외에도 많이 사용된다. 부모 정점을 찾는 find 함수와,서로 다른 부모 정점을 가지는 집합을 합치는 Union 함수로 이루어져 있다.

 

난 오늘 크루스칼을 제대로 이해하지 못했다. 그래서 강의를 보고 구글링을 한 결과 지금은 어느정도 이해하기 시작했다.

그러나 문제풀때는 그러하지 못해서 프림으로 문제를 해결했다.

 

1. 네트워크 연결 https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

import heapq

def network():
    
    N = int(input())
    M = int(input())

    edge = [[] for _ in range(N + 1)]

    for _ in range(M):
        a, b, c = map(int, input().split())
        edge[a].append((c, b))
        edge[b].append((c, a))

    heap = [(0, 1)]
    rs = 0
    chk = [False] * (N + 1) 

    while heap:
        cost, node = heapq.heappop(heap)
        if not chk[node]:
            chk[node] = True
            rs += cost
            for next_cost, next_node in edge[node]:
                heapq.heappush(heap, (next_cost, next_node))

    return rs

 

평범하게 프림으로 해결했다. 프림으로 문제를 풀다보니 기본코드를 알면 그 코드만으로 문제가 거의 풀린다는 것이었다. 그래서 기본코드를 꼭 외워야 한다.

 

 

2. 도시 분할 계획 https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

import heapq

def city():
    N,M = map(int, input().split())
    edge = [[] for _ in range(N+1)]

    for i in range(M):
        a,b,c = map(int, input().split())
        edge[a].append([c,b])
        edge[b].append([c,a])

    heap = []
    heap.append((0,1))
    chk = [False]*(N+1)
    rs = []

    while heap:
        w, each_node = heapq.heappop(heap)
        if chk[each_node] == False:
            chk[each_node] = True
            rs.append(w)
            if len(rs) == N:
                break
            for next_cost, next_edge in edge[each_node]:
                heapq.heappush(heap, (next_cost,next_edge))

    return sum(rs) - max(rs)

print(city())

*강의 참조
https://www.youtube.com/watch?v=nZ4RTuoHS_Y

 

크루스칼이 제대로 이해가 되지 않아 MST에 대한 자료를 찾던 중 유튜브 강의가 있길래 참고했는데 쉽게 설명하고 프림에 대해 잘 설명이 되어 있어서 이 영상을 본 후 프림으로 수월하게 해결했다. 리스트를 0번 부터가 아닌 1번부터 사용해야 하니까 N+1로 해줬고 즉 [0]번은 사용되지 않는다.

 

3. 행성 연결 https://www.acmicpc.net/problem/16398

16398번: 행성 연결

import heapq

def planet():
    N = int(input())
    edge = [[] for _ in range(N+1)]
    chk = [False] * (N+1)
    rs = 0

    for _ in range(N):
        weights = list(map(int, input().split()))
        for idx, weight in enumerate(weights):
            if weight != 0:
                edge[_+1].append((weight, idx+1))

    heap = [(0, 1)]
    while heap:
        w, each_node = heapq.heappop(heap)
        if chk[each_node] == False:
            chk[each_node] = True
            rs += w
            for next_edge in edge[each_node]:
                if not chk[next_edge[1]]:
                    heapq.heappush(heap, next_edge)

    return rs

print(planet())

 

3번과 거의 동일하나 차이가 있다면 input방식이 좀 다르다. 입력값을 weights에 list로 저장했고 enumerate를 사용해서 index와 값을 다 확인하게 했다. edge[_+1].append((weight, idx+1)) 이 부분은 위와 마찬가지로 1번 행성부터 쓰이니까 인덱스 값에 1을 더했고 다음 행성의 인덱스도 1을 더해줬다.

 

 

오늘은 문제자체는 꽤 수월하게 풀었다. 다만 크루스칼이나 Union-Find에 대해 이해가 잘 되지 않아 꽤나 고생했다. 앞으로도 개념적으로 어려운것들이 계속 나올텐데 다른건 몰라도 코드를 직관적이로 봤을때 이해하는 능력이 빨리 길러졌으면 좋겠다고 수없이 생각했다...

 

 

*드림핵

 보안에 관심이 있는 편이라 시작을 어떻게 할수 있냐는 질문을 했고 해당 사이트를 추천해주셨다. 지금 과정이 벅차 지금 당장은 무리이고 이 과정이 끝나면 시작해봐야겠다.