LEVEL3/섬 연결하기

Q·2021년 10월 16일
0

문제 설명


문제


문제링크

전체 코드

def solution(n, costs):
    costs.sort(key=lambda x:x[2])
    routes = set([costs[0][0],costs[0][1]])
    answer = costs[0][2]

    while n != len(routes):
        for i, v in enumerate(costs[1:]):
            if v[0] in routes and v[1] in routes:
                continue

            if v[0] in routes or v[1] in routes: 
                routes.update([v[0], v[1]])
                answer += v[2]
                costs[i+1] = [-1,-1,-1]
                break

    return answer

해결 방법

Kruskal알고리즘 문제

Kruskal 알고리즘에서 핵심은 사이클이 생성되지 않게하는 것이다.
사이클이 생성되지 않기 위한 조건으로는 추가하려는 간선의 양끝점이 같은 집합에 속하지 않는 것이다.

그래서 코드를 보면 먼저 비용을 기준으로 costs를 오름차순 정렬을 해준 뒤 routes에 첫 번째 경로 양 끝 집합을 넣어준다. 그리고 while문을 사용하고 그 안에 for문을 사용하여 costs[1:]을 돌린다. 그리고 추가하려는 간선의 양끝점이 routes에 있다면 continue를 하고 그게 아닌 양끝점중 하나만 routes에 있다면 routes를 그 양끝점으로 update를 해주고 비용을 더해준다. 그리고 그 costs값을 [-1,-1,-1]로 초기화 시켜준다.

profile
Data Engineer

0개의 댓글