💡 문제 해결 아이디어

✨ 내가 생각한 아이디어

• Minimum Spanning Tree 문제이다.
• 카테고리가 Greedy이기 때문에, Kruskal Algorithm으로 풀어보자 (Prim도 가능)
• Kruskal을 모른다면, 다른 좋은 블로그들에서 검색해보자... 나는 역량이 😂

1. list를 통한 각 섬의 forest 구현
2. 비용에 대해서 오름차순으로 경로를 정렬
3. total = 0
4. for road in roads:
   • 만약(if) 경로의 양 끝 섬의 parent가 다르면,
     - 두 섬을 union(rank가 더 큰 쪽으로)
     • total += cost
5. return total

🛠 피드백

• rank를 고려해야하는 이유는, 문어(rank가 높은 set)와 솔로(rank가 0인 set)가 있는데, 솔로가 문어발의 끝에 붙어서 이어지지 않고 문어의 발 중 하나가 솔로에게 붙는 황당한 경우가 생길 수 있다.

💻 작성된 코드

def solution(n, costs):
    
    # set의 부모를 찾으면서 최종 부모로 연결도 해주는 함수
    def find_p(x):
        if x != forest[x][0]:
            forest[x][0] = find_p(forest[x][0])
        return forest[x][0]
    
    # 두 set의 rank를 비교해서 큰 쪽으로 union 해주는 함수
    def union(x, y):
        rank_x = forest[find_p(x)][1]
        rank_y = forest[find_p(y)][1]
        if rank_x >= rank_y:
            forest[find_p(y)][0] = find_p(x)
            rank_x += 1
        else :
            forest[find_p(x)][0] = find_p(y)
            rank_y += 1
    
    # [i는 parent, 0는 해당 set의 rank]
    forest = [[i, 0] for i in range(n)]
    
    # 비용을 기준으로 오름차순 정렬
    costs.sort(key=lambda x: x[2])
    # 총 비용
    total = 0
    
    for road in costs:  
    	# 두 섬이 연결되어있지 않으면 (부모가 다르면)
        if find_p(road[0]) != find_p(road[1]):
        	# 연결(union)하고 총 비용에 해당 경로의 비용을 추가
            union(road[0], road[1])
            total += road[2]
    
    return total