[파이썬] 섬 연결하기

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

 

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

 

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

 

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

👩‍🦰 나의 풀이

 

# 실패
def solution(n, costs):     # 섬의 개수, 비용
    answer = 0
    costs.sort(key=lambda x : x[2]) # 비용이 낮은 순
    visited=[0]*n
    
    for c in costs :
        if visited[c[0]] == 0 or visited[c[1]] == 0  :
            visited[c[0]] =1
            visited[c[1]]=1
            answer+=c[2]
    return answer

 

visited 리스트에 방문한 섬을 1로 표시했다.

 

 

👱‍♂️ 다른사람 풀이

 

# 출처 : https://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
def solution(n, costs):     # 섬의 개수, 비용
    ans=0
    # cost 기준으로 오름차순 정렬
    costs.sort(key=lambda x : x[2])
    routes=set([costs[0][0]])
    while len(routes) != n :
        for i, cost in enumerate(costs) :
            if cost[0] in routes and cost[1] in routes :
                continue
            if cost[0] in routes or cost[1] in routes :
                routes.update([cost[0], cost[1]])
                ans+=cost[2]	# 다리 건설 비용
                costs[i]=[-1, -1, -1]
                break
    return ans

 

Kruskal  알고리즘 이용.

routes에 cost[0] 또는 cost[1]이 있으면 routes를 업데이트한다.

둘 다 있으면 continue

cost 기준으로 오름차순 정렬하고 시작했기 때문에 최소 비용을 구할 수 있다.

costs[i]=[-1, -1, -1]할 필요가 없다. routes로 방문 여부를 확인하니까

섬을 연결한 후 break를 해야 최소 비용이 구해진다. (다시 비용이 작은 순으로 보니까)

 

 

# 출처 : https://codedrive.tistory.com/164
def solution(n, costs):     # 섬의 개수, 비용
    costs.sort()
    connect=[costs[0][0]]
    answer=0
    
    while len(connect) != n :
        temp=1000000000000000
        idx=0
        for i in range(len(costs)) :
            if costs[i][0] in connect or costs[i][1] in connect :
                if costs[i][0] in connect and costs[i][1] in connect :
                    continue
                if temp > costs[i][2] :
                    temp=costs[i][2]
                    idx=i
        
        answer+=temp
        connect.append(costs[idx][0])
        connect.append(costs[idx][1])
        connect=list(set(connect))
        costs.pop(idx)
    return answer

 

Kruskal  알고리즘 이용.

costs를 반복하면서 connect에 섬이 있는지 확인한다. 

temp가 더 크면 temp를 더 작은 값인 costs[i][2]로 갱신한다.

 

 

# 출처 : http://blog.naver.com/PostView.nhn?blogId=jaeyoon_95&logNo=221872563653&categoryNo=74&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView
def solution(n, costs):     # 섬의 개수, 비용
    answer=0
    costs.sort(key=lambda x : x[2])
    connection=[costs[0][0]]
    
    while len(connection) != n :
        for i, cost in enumerate(costs) :
            if (cost[0] in connection) and (cost[1] in connection) :
                continue
            if (cost[0] in connection) or (cost[1] in connection) :
                answer+=cost[2]
                connection.append(cost[0])
                connection.append(cost[1])
                connection=list(set(connection))
                costs.pop(i)
                break
    return answer

첫 번째 풀이랑 알고리즘은 같음.

costs를 pop할 필요없음

 

 

 

출처 💁‍♀️ 프로그래머스