[Python/프로그래머스]섬 연결하기_Greedy(그리디)

 

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

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

 

 

 

Kruskal 알고리즘을 이용해 풀이하였다. 

 

1. 비용이 작은 순으로 정렬한다. 

2. connect set을 만들어 연결 여부를 확인한다. 

3. while문을 통해 전부 연결될 때까지 돌린다.

    3-1. cost에 이미 있으면 continue

    3-2. cost에 없으면 connect 에 넣고 비용을 더한다. 

4. 비용 반환 

 

 

 

 

 

코드 : 

 

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x : x[2]) # 비용 기준 정렬
    connect = set([costs[0][0]]) # 연결확인용 set (set은 중복 불가)
    
    while len(connect) != n: # 전부 다 연결되지않을 동안 
        for cost in costs :
            if cost[0] in connect and cost[1] in connect :   # 이미 있는 경우
                continue
            if cost[0] in connect or cost[1] in connect : # 한개만 있는경우
                connect.update([cost[0], cost[1]]) # 값을 여러개 추가 
                answer += cost[2] 
                break # 다시 costs를 처음부터 돌린다.
    return answer

 

 

여기서 answer를 update할 때 왜 break를 하는지 이유를 몰랐었다. 

 

 

이에 대한 반례는 ( n =6 )

costs = [[0, 1, 5], [0, 3, 2], [0, 4, 3], [1, 4, 1], [3, 4, 10], [1, 2, 2], [2, 5, 3], [4, 5, 4]] 이다.

break를 넣으면 11, break를 넣지않으면 19이다. 

 

 

즉 , break를 넣은 이유는

이전에 그냥 지나갔던 ( cost[0], cost[1]이 아무것도 connect에 없던 )친구들을 다시 확인하기 위해서이다.

 

 

break 잊지말자-! 

 

 

 

 

 

배운 점 :

 

1. set의 update 

 

set에 여러 개의 원소를 한번에 넣고 싶다면 update를 사용하면 된다.

connect.update([cur[0],cur[1]])

이렇게 [ ]로 감싸야한다. 

 

update를 사용하기 싫다면 add를 이용해서 하나씩 넣어도 통과한다. 

 

 

< add사용 코드 >

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x : x[2])
    connect = set([costs[0][0]])
    
    while len(connect) < n :
        for cur in costs :
            if cur[0] in connect and cur[1] in connect :
                continue
            elif cur[0] in connect or cur[1] in connect :
                answer += cur[2]
                connect.add(cur[0])
                connect.add(cur[1])
                break

    return answer

 

 

 

 

 

 

참고 블로그  :

 

https://soohyun6879.tistory.com/145

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

 

 

 

복습 : 

✅ 20220622

✅ 20220624

✅ 20220626

✅ 20220627