[프로그래머스] 섬 연결하기 파이썬 풀이

 

※사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

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

 

 

---

 

 

 

문제 설명

◇ 전형적인 크루스칼 알고리즘 문제이다.

◇ 크루스칼 알고리즘이란? 그래프 내의 모든 정점을 가장 적은 비용으로 연결하는 알고리즘으로 최소 신상 트리를 구하는 알고리즘이다.

◇ 비용을 기준으로 costs를 오름차순으로 정렬하고 해당 간선을 방문했는지 안 했는지 확인해가며 풀어가는 문제이다.

 

 

---

 

 

문제 풀이 (with Python)

def solution(n, costs):
    costs=sorted(costs, key=lambda x:x[2])
    
    node=set([costs[0][0],costs[0][1]])
    total=costs[0][2]
    
    while len(node)!=n:
        for i in range(1,len(costs)):
            if costs[i][0] in node and costs[i][1] in node:
                continue
            if costs[i][0] in node or costs[i][1] in node:
                node.update([costs[i][0],costs[i][1]])
                total+=costs[i][2]
                break
                
    return total

◇ costs를 비용을 기준으로 오름 차순으로 정렬한다. 

 

◇ node에 costs의 첫 번째 노드 연결 정보를 넣는다. (연결된 간선 정보를 넣다 보면 중복으로 노드 값이 들어갈 수 있기 때문에 set을 통해 중복 값을 배제해준다.)

 

◇ total에 가중치 값을 넣는다.

 

◇ for문의 시작이 1부터 하는 이유는 costs의 0번째에 있는 정보는 이미 위에서 전부 넣어줬기 때문이다.

 

◇ for문 안 if 조건 문 같은 경우, 두 개의 노드가 전부 node안에 있어야 하고 하나라도 없는 경우 연결을 위해 가중치값을 더해야 하므로 둘 중 하나만 있을 경우에는 node에 간선 정보를 넣고 total에 가중치 값을 더한다.

 

◇ 가중치 값이 더해지면 break로 for문 순회를 멈추고 모든 노드를 순회했는지 확인 후 노드를 전부 순회하지 않았다면 다시 1번부터 차근히 for문을 돌린다.