[프로그래머스] 섬 연결하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 모든 섬이 이어질 때 그 비용이 최소가 되어야 한다.

비용이 최소가 되어야 하므로 그리디 알고리즘을 활용하여 비용이 작은 것부터 섬을 연결하면 된다.

하지만 여기서 섬들을 연결할 때 사이클이 존재하면 안 되기 때문에 이를 방지하고자 크루스칼 알고리즘을 활용하여 문제를 해결한다. 이를 유니온 파인드(union-find) 알고리즘으로 해결한다.

 

유니온 파인드 알고리즘은 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

union 연산은 각 노드가 속한 집합을 1개로 합치는 연산이다.

find 연산은 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다.

유니온 파인드 알고리즘을 사용하면 모든 노드가 하나의 대표 노드에 직접 연결되는 형태로 변경된다.

 

1. find 연산을 구현 def find(x)
2. 만약 해당 노드 x의 대표 노드가 x랑 다르면 if (parent[x] != x)
   1. x의 대표 노드를 현재 x 노드의 대표 노드를 넣어 제일 높은 대표 노드를 찾는다. parent[x] = find(parent[x])
3. 반면에 해당 노드 x가 대표 노드 x이면 그대로 노드 x의 대표 노드를 반환한다. return parent[x]
4. union 연산을 구현 def union(v1, v2)
   1. 노드 v1의 대표 노드를 v1에 저장한다. v1 = find(v1)
   2. 노드 v2의 대표 노드를 v2에 저장한다. v2 = find(v2)
   3. 만약 v1 값과 v2 값이 다르면 v1을 v2의 대표 노드로 변경한다. (연결) if (v1 != v2): parent[v2] = v1
5. 각 노드의 대표 노드를 저장할 리스트를 생성하는데, 처음에는 자기 자신이 대표 노드가 된다. parent = list(i for i in range(n))
6. 비용이 최소가 되어야 하므로 비용을 기준으로 오름차순 정렬을 한다. costs = sorted(costs, key = lambda x : x[2])
7. 정렬한 costs의 원소를 하나씩 가져오며 for i in costs
   1. 각 노드의 위치와 비용을 분리한다. v1, v2, cost = i
   2. 만약 각 노드에서의 현재 연결된 노드의 정보가 다르면 if (find(v1) != find(v2))
      1. 사이클이 발생하지 않는 경우이므로 두 노드를 새로 연결한다. union(v1, v2)
      2. 새로 선을 포함시켰으므로 해당 선의 비용을 전체 비용에 더해준다. answer += cost

3. 소스코드

def solution(n, costs):
    answer = 0
    
    def find(x):
        if (parent[x] != x):
            parent[x] = find(parent[x])
        
        return parent[x]
    
    def union(v1, v2):
        v1 = find(v1)
        v2 = find(v2)

        if (v1 != v2):
            parent[v2] = v1
		
    parent = list(i for i in range(n))

    costs = sorted(costs, key = lambda x : x[2])
    
    for i in costs:
        v1, v2, cost = i
        if (find(v1) != find(v2)):
            union(v1, v2)
            answer += cost
            
    return answer