[LV2] 프로그래머스 문제풀이 섬 연결하기

프로그래머스로 코딩테스트 뽀개기

https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

 

해당 문제는 프림 알고리즘과 크루스칼 알고리즘을 활용하여 해결할 수 있다.

 

먼저 프림 알고리즘을 살펴보자

# 프림 알고리즘

import heapq as hq


def solution(n, costs):
    graph = {}
    # 직전 노드 - 방문 노드 체크에도 사용
    pi = {}
    # 해당 노드에 접근하는데 필요한 비용 - 다익스트라에서는 시작점에서 해당 점으로의 거리로 변경
    d = {}
    answer = 0
    # 프림 알고리즘은 지도를 만들어준다.
    for f, t, c in costs:
        graph[f] = graph.get(f, []) + [(t, c)]
        graph[t] = graph.get(t, []) + [(f, c)]
    heap = []
    # 시간 복잡도 감소를 위해 힙을 사용한다.
    hq.heappush(heap, (0, 0, 0))
    while heap:
        cost, cur, org = hq.heappop(heap)
        if cur in pi: continue
        d[cur] = cost
        pi[cur] = org
        for t, c in graph[cur]:
            if t in pi: continue
            hq.heappush(heap, (c, t, cur))
             # 참고 - 다익스트라 - 이 문제는 절대 다익스트라가 아님! 
             # 원점에서 직접 가거나 원점에서 이전 점을 들러서 해당 노드에 가는 방법의 최소값
             # 원점에서 직접 가기 d[t] // 이 문제에서는 이 점으로의 간선비용.
             # cost + c 이전 간선을 거쳐 해당 간선으로 가는데 필요한 비용
             # cost - 현재 노드에 도착하는데 필요한 비용 (다익스트라에서는 연속, 여기서는 간선)
             # hq.heappush(heap, (min(d[t], cost + c), t,cur))
    return sum(d.values())


print(solution(4, [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]))

 

다익스트라를 공부하기 위해선 먼저 프림 알고리즘을 공부한다

 

프림에서는 d[x] 는 x로 도달하는데 소요되는 비용이 "직전 점"에서 해당 점으로 이동하는데 소요.

다익스트라는  "시작 점"에서 해당 점으로 이동하는데 소요.

따라서 프림은 간선 비용을 그대로 힙에 넣어주면

hq.heappush(heap, (c, t, cur))

알아서 비용 중 최소 값이 선택되며 더 큰 비용은 방문 체크에 의해 무시된다.

(파이썬은 min heap)

 

다익스트라는 처음에 해당 점까지의 거리를 초기화 해서 d 배열에 저장한다.

그 후 방문 처리 하면서 d를 갱신해준다.

hq.heappush(heap, (min(d[t], cost + c), t,cur))

실제적인 활용법은 "가장 먼 노드" 문제풀이에서 다룬다.

 

해당 알고리즘의 시간 복잡도는 힙에서 정점 찾아오기 (logV) * 정점의 수(V) + 간선의 수(E)*힙삽입(logV) 

= O(VlogV + ElogV) = O(ElogV) (간선의 갯수가 정점의 갯수에 비해 많은가 적은가에 따라 다르겠다만 E가 V보다 많을 수 있음.)

 

따라서 간선 갯수가 적을수록 유리하다.

 

자세한 설명은 해당 포스트를 참고하라.

https://victorydntmd.tistory.com/102

[알고리즘] MST(3) - 프림 알고리즘 ( Prim's Algorithm )

왜 for는 내부 루프인데 더하냐? 이유는 최대 수행 횟수가 정해져 있기 때문이다. for 는 최대 간선 갯수 만큼만 수행된다. (양쪽이면 2배겠지)

 

반대로 크루스칼 알고리즘은 간선을 기준으로 더해서 트리를 만든다.

어떻게 mst가 만들어지는가?에 대한 증명은 여러번 봐도 이해는 되나 암기가 안된다. ㅠ

일단 먼저 문제 풀이를 보고 가슴으로 받아들인 뒤 나중에 찾아보자.

 

이 알고리즘의 핵심은 rank를 이용해 경로를 압축하는 것이다.

find_parent 함수 사용을 통해 경로 압축을 설정하거 설정하지 않을 수 있다.

6번 같은 경우 갱신하지 않으면 부모가 계속 5로 유지된다.

보면 알겠지만 계속 부모를 가리키도록 경로가 압축되기 때문에 높이가 최대 log(v)다

0을 초기값으로 두면 (알고리즘은 0으로 초기화)

1짜리 2개 붙이면 1이 되고 (log2)

(4일 때 1개짜리 1개 하면 높이 2(log4), 8일때 2개짜리 2개 붙이면 높이 3..(log8))

경로압축을 하지 않으면 높이는 최대 n 까지 가능하다.

(1-2-3-4-5-6-7-8)

이 방법을 통해 부모가 같으면 간선을 포함하고 아니면 배제한다.

 

parent = {}
rank = {}

# 집합 및 높이 초기화
def make_set(v):
    parent[v] = v
    rank[v] = 0


# 부모 찾기
def find_parent(v):
    if parent[v] != v:
    	# 부모가 루트가 아니면
        # 부모의 부모찾기 경로압축
        parent[v] = find_parent(parent[v])
        # 루트 부모 리턴
    return parent[v]


def union(r1, r2):
    if r1 != r2:
        if rank[r1] > rank[r2]:  # 깊은 쪽에 붙여줘야 나무가 된다.
            parent[r2] = r1  # r1의 키가 자란다
        else:
            parent[r1] = r2  # r2의 키가 자란다.
            if rank[r1] == rank[r2]:
                rank[r2] += 1


def solution(n, costs):
    answer = 0
    for i in range(n):
        make_set(i)
    for u, v, cost in sorted(costs, key=lambda x: x[2]):
        root1, root2 = find_parent(u), find_parent(v)
        # 부모가 같으면 간선에 추가하지 않는다
        if root1 != root2:
            union(root1, root2)
            answer += cost
    return answer