[파이썬] 프로그래머스 Level.3 | 탐욕법(greedy) | 섬 연결하기

탐욕법을 이용한 최소신장거리 탐색은 여러 가지 알고리즘이 있다.

처음에 프림(Prim) 알고리즘을 이용하여 코드를 짰는데 몇 가지 통과 못하는 케이스들이 있어서 다른 알고리즘을 이용했다. 

 

<Prim 알고리즘을 이용한 풀이> 

이는 정확도도 낮고 코드도 불필요하게 길었던 것 같다.

def setting(list1):
    list2=[]
    for i in list1:
        if i not in list2:
            list2.append(i)
    return list2
    
def solution(n, costs):
    answer = 0
    visit=[] #visit에 n개 들어오면 끝
    next_visit=[]
    
    sort_costs=sorted(costs,key=lambda x : x[2])
 
    visit.append(sort_costs[0][0]); visit.append(sort_costs[0][1])
    answer+=sort_costs[0][2] #answer
 
    del sort_costs[0]
    
    while(True):
        next_visit=[]
        for candidate in sort_costs: #후보 next_visit 구하기
            for j in visit:
                if candidate[0]==j or candidate[1]==j:
                    next_visit.append(candidate)
                    
        next_visit=setting(next_visit)           
        sort_nextvisit=sorted(next_visit,key=lambda x:x[2])
 
        answer+=sort_nextvisit[0][2] #answer
        
        visit.append(sort_nextvisit[0][0]); visit.append(sort_nextvisit[0][1])
        set_visit=set(visit)
 
        if len(set_visit)==n:
            break
        sort_costs.remove(sort_nextvisit[0])        
 
        
    return answer

그림과 같이 정확도가 낮다.

 

다른 방법은 다른 풀이를 참고하여 작성하였다. 

이전 코드와 달리 시간복잡도가 훨씬 효율적이었다.

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2])
    visited = [0] * n
    visited[0] = 1 #임의의 하나 일단 1로 둠. =visit함 
    while sum(visited) != n:
        for cost in costs:
            s, e, c = cost #start, end, cost
            if visited[s] or visited[e]: #start, end 둘 중 하나 1이면 
                if visited[s] and visited[e]: #그 중에서도 start, end 둘다 1이면 
                    continue #둘이 연결되었다는 거니까 그냥 넘어감.
                else: #둘중 하나만 1이면 
                    visited[s] = 1 #둘다 visit됨 처리. 
                    visited[e] = 1
                    answer += c #answer 
                    break
    return answer