[프로그래머스]섬 연결하기 - 그리디, 최소 신장 트리, Kruskal

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

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

 

# 크루스칼 알고리즘
def solution(n, costs):
    answer = 0
    visited = [0]
    # 크루스칼 알고리즘 적용을 위해 가중치를 오름차순으로 정렬한다
    costs.sort(key=lambda x: x[2])
    
    # 방문한 정점의 갯수가 n이 된다면 반복문을 중단
    while len(visited) < n:
        for cost in costs:
            s, e, c = cost
            # 시작점과 끝점중 하나라도 방문한 리스트에 들어 있을 경우
            if s in visited or e in visited:
                # 사이클이 발생되는 조건
                if s in visited and e in visited:
                    continue
                # 사이클이 발생되지 않을경우 방문 표시
                else:
                    if s not in visited:
                        visited.append(s)
                    if e not in visited:
                        visited.append(e)
                    answer += c
                    # 이미 연결이 되었으므로 break 후 다음 연결
                    break
    return answer

 

문제 해결 Point

해당 문제의 유형은 최소 신장트리를 구하는 것으로 상당히 명확하다고 할 수 있다. 최소 신장트리를 구하는 알고리즘에는 두가지가 존재한다.

1. 프림 알고리즘
2. 크루스칼 알고리즘

이번 문제에는 크루스칼 알고리즘을 통해 풀이해보겠다. 크루스칼 알고리즘에 대해서는 이미 알고있는 상태로 가정하겠다.

 

그럼 위의 코드를 순서대로 풀어 설명해보겠다.

1. visited 리스트에는 방문한 노드를 넣어둔다. 시작 노드는 0으로 설정한다.
2. 크루스칼 알고리즘의 적용을 위해 가중치를 기준으로 하여 오름차순으로 costs를 정렬한다.
3. 방문한 정점의 갯수가 n이 될때 까지 반복을 수행한다.
   1. 만약 시작 노드나 끝 노드중 하나라도 방문한 노드에 들어 있다면 다음 조건을 수행한다.
      -> 인접한 노드를 필터링 하는 조건
      1. 만약 시작노드와 끝 노드 모두 방문한 노드에 들어 있다면 이미 사용된 간선이므로
         사이클이 생길 수 있어 continue 한다.
      2. 아니라면, 방문 리스트에 노드를 넣고, 가중치를 더하고 다음 반복을 수행한다.

최소 신장트리를 구현하는 알고리즘을 정확히 알아야 풀 수 있는 문제이다. 다음에는 프림 알고리즘을 이용해서도 풀이해보려고 한다.

---

정석 크루스칼 알고리즘

위의 풀이와 다르게 유니온 파인드 알고리즘을 활용한 정석이 되는 크루스칼 풀이 방법도 추가하였다.

 

# 크루스칼 알고리즘, 유니온파인드 알고리즘 활용

def solution(n, costs):

    # 특정한 노드의 부모가 누구인지 찾는 함수
    def find_parent(parent, target):
        if target == parent[target]:
            return target

        parent[target] = find_parent(parent, parent[target])
        return parent[target]

    # 노드를 합칠 때 부모가 더 작은 값으로 합치는 함수
    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

    answer = 0
    
    # 해당 정점의 부모노드가 누구인지 적혀있는 리스트
    parent = [i for i in range(n)]
    
    # 크루스칼을 가중치가 적은 것 부터 더해나감
    costs.sort(key=lambda x : x[2])

    for cost in costs:
        s, e, w = cost
        # 부모노드가 같다면 사이클이 생김, 따라서 같지 않은 경우에만 수행
        if find_parent(parent, s) != find_parent(parent, e):
            answer += w
            union_parent(parent, s, e)

    return answer

 

문제해결 Point

크루스칼의 알고리즘에서 사이클이 발생하는지에 대한 여부를 유니온 파인드 알고리즘을 통해 알아내는 방법이다. 해당 알고리즘은 이미 알고 있다는 가정하에 설명을 진행한다.

 

1. 특정한 노드의 부모가 누구인지 찾아주는 find 함수, 노드를 합칠 때 부모가 더 작은 값으로 합쳐주는 union 함수를 정의한다.
2. parent 리스트에는 각 정점의 부모노드가 누구인지 적혀있고, 초기에는 자기 자신으로 설정한다.
3. 크루스칼 알고리즘이기에 가중치 순으로 정렬을 진행해둔다.
4. 정렬된 배열을 순회하면서, 두 정점의 부모노드가 다를 경우에만 가중치를 더하고, union 함수를 호출해 합쳐준다.
5. 반복문이 끝나면 정답을 도출할 수 있다.