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

1. 문제 - 프로그래머스 섬 연결하기

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

 

해당 문제는 유니온-파인드, 그리디 알고리즘을 사용하여 풀이할 수 있는 문제이다.

 

1) 섬 사이에 다리를 건설하는 비용이 주어질 때, 최소 비용으로 모든 섬이 서로 통행할 수 있도록 함 --> 그리디

2) 섬과 섬 간의 연결관계가 있을 때, 모두를 통행(하나의 집합으로 만들기)하도록 한다  --> 유니온-파인드

3) 비용을 최소화 하기 위해, 다리를 추가 시 사이클을 형성하지 않도록 한다 --> 파인드를 통해 사이클 판단

 

*사이클이란, 집합 내 노드끼리 순환하는 구조를 의미한다.

- 집합 내 각 노드의 부모 노드가 모두 같을 경우, 사이클을 이룬다고 말할 수 있다.

 

✅ 풀이 과정

 

1) 유니온-파인드 함수

    parent = [i for i in range(n)]   # 처음에는 다 자기 자신이 부모 노드임
    rank = [0] * n   # 유니온파인드의 기준이 될 rank 배열
        
    def find(i):
        if parent[i] == i:    # 자기 자신이 곧 부모 노드이다 == 루트 노드
            return i
        
        parent[i] = find(parent[i])   # 각 노드의 부모 노드를 루트 노드로 통일한다.
        return parent[i]
    
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        
        if rank[root_x] < rank[root_y]:   # x 루트노드 랭크보다 y 루트노드 랭크가 더 크면 y가 속한 집합에 x 집합을 합쳐야 하므로
            parent[root_x] = root_y       # x의 루트노드 부모를 y 루트노드로 지정한다.
        else:
            parent[root_y] = root_x       # 위와 반대
            if rank[root_x] == rank[root_y]:   # 만약에 랭크가 같으면 둘 중 하나의 집합의 랭크를 높여야하는데, 이 경우 x 집합에 y 집합을 포함시키는 것이므로
                rank[root_x] += 1      # x의 루트노드 랭크를 +1  한다.

 

 

2) 문제에 조건의 맞게 코드 작성

    answer = 0
    edges = 0
    costs.sort(key=lambda x:x[2])    # 1. 최소 비용으로 연결시키기 위해, 비용순으로 배열을 정렬한다.
    
    for node1, node2, cost in costs:
        if edges == n-1:    # 연결한 간선이 섬의 갯수-1이라는 것은 모두 연결했다는 의미이므로 여기서 break
            break
            
        x = find(node1)    # x와 y의 루트노드를 찾는다.
        y = find(node2)
        
        if x != y:    # 사이클 순환을 방지 --> 루트 노드가 다른지 확인
            union(x, y)   # 각각 x와 y를 루트 노드로 가지는 집합을 합친다.
            
            answer += cost   # 비용 더하기
            edges += 1      # 연결했으므로 간선 더하기
            
    return answer