[Programmers] 섬 연결하기

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

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

 

파이썬을 사용했습니다.

 

문제를 풀때 가장 중요한 부분이 사이클이 없고 분리된 섬 없이  모든 섬이 연결되는 것입니다.

문제를 푼 방법은 먼저 다리를 연결하는 값을 오름차순으로 정렬한 뒤 한번 연결된 섬을을 미리 정의한 그룹에 넣는 것입니다. 또한 연결하려는 양 끝 섬이 이미 정의한 그룹안에 있다면 다리를 건설 하는 것을 포기합니다. 

알고리즘은 Kruskal 알고리즘으로 분류됩니다.

https://ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전

 

---

---

정답 코드

def solution(n, costs):
    answer = 0
    costs = sorted(costs,key = lambda x: x[2])
    set_target = set([costs[0][0]])
    
    while len(set_target) < n:
        for i, val in enumerate(costs):
            if val[0] in set_target and val[1] in set_target:
                continue
                
            if val[0] in set_target or val[1] in set_target:
                set_target.update([val[0], val[1]])
                answer += val[2]
                costs[i] = [-1, -1, -1]
                break
    
    return answer

 

 

참고링크

• jisun-rea.tistory.com/entry/python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Level3-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0-%ED%83%90%EC%9A%95%EB%B2%95
• lipcoder.tistory.com/entry/%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4