[프로그래머스 / 그리디 / Python] 섬 연결하기

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

---

풀이 코드

def solution(n, costs):
    answer = 0
    # 특정 원소가 속한 집합을 찾기
    
    def find_parent(parent, x):
        # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
        return parent[x]

    # 두 원소가 속한 집합을 합치기
    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


    parent = [0] * n # 부모 테이블 초기화하기



    # 부모 테이블상에서, 부모를 자기 자신으로 초기화
    for i in range(n):
        parent[i] = i


    # 간선을 비용순으로 정렬
     
    costs = sorted(costs, key=lambda x:x[2])

    # 간선을 하나씩 확인하며
    for edge in costs:
        a, b, cost = edge
        # 사이클이 발생하지 않는 경우에만 집합에 포함
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            answer += cost

    return answer

---

풀이 과정

 

최소신장트리를 찾는 kruskal알고리즘을 이용하였다.

 

Kruskal 알고리즘 (NlogN)

 

1. 간선 데이터를 비용에 따라 오름차순 정렬

 

2. 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인

① 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.

② 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. (X)

 

3. 모든 간선에 대해 2번 과정 반복

 

최소신장트리?

• 신장트리란, 사이클을 형성하지 않고 그래프의 모든 정점(V)이 간선(E)으로 연결되어 있는 것
• 최소신장트리란 최소한의 비용으로 신장트리를 형성하는 것

 

 

간선 (1,2) (1,3) (2,3) (2,4) (3,5) (4,5)

1. 비용이 가장 최소인 (1,2)를 선택한 후 1번 노드와 2번 노드에 대해 union 함수를 수행한다.
2. 그 다음 최소인 (1,3)노드에 대해 union함수를 수행한다.
3. 그 다음 최소인 (2,3)을 처리하면 사이클이 발생하기 때문에 (2,3)을 연결하지 않는다.
4. 이후 (2,4)를 처리한다.
5. 이후 (3,5)를 처리한다
6. 이후 (4,5)를 연결하면 사이클이 발생하기 때문에 연결하지 않는다.

 

최종 결과는 4-2-1-3-5 순으로 연결 (역도 성립)

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력 받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    # 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((cost, a, b))

# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

print(result)

 

 

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

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