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

 

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

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

읽자마자 그냥 MST인거 알았음

MST 구현 알고리즘에는 프림 알고리즘, 크루스칼 알고리즘이 있음

 

크루스칼 하다가 중간에 막혀서 프림으로 구현함

파이썬으로 코테 준비한지 얼마안됐는데, 자료형 집합쓰면 편하겠다고 바로 생각해낸게 뭐랄까 기뻤음

 

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

 

정확성 테스트

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (0.05ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.2MB)
테스트 6 〉	통과 (0.05ms, 10.3MB)
테스트 7 〉	통과 (0.06ms, 10.2MB)
테스트 8 〉	통과 (0.02ms, 10.3MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0

 

목요일에 크루스칼 재도전하고 그리디 마무리할거

수요일은 공부안하는날