프로그래머스 섬 연결하기

문제 설명

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):
    cost = 0
    island = [i for i in range(n)]
    visited = [0 for i in range(n)]
    
    costs = [c for c in costs if c[2] != 0]
    costs.sort(key=lambda x:x[2])
    
    for i in range(len(costs)):
        isl1 = min(costs[i][0],costs[i][1])
        isl2 = max(costs[i][0],costs[i][1])
        
        #print(island, "cost:",cost)
        #print(visited, "find:", isl1, "->", isl2)
        
        if visited[isl1] == 1 and visited[isl2] == 1:
            if island[isl1] != island[isl2]:
                source = island[isl2]
                target = island[isl1]
                for z in range(len(island)):
                    if island[z] == source:
                        island[z] = target
                cost += costs[i][2]
        elif visited[isl1] == 0 or visited[isl2] == 0:
            visited[isl1] = 1
            visited[isl2] = 1
            source = island[isl2]
            target = island[isl1]
            for z in range(len(island)):
                    if island[z] == source:
                        island[z] = target
            cost += costs[i][2]
    
    return cost

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.4MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.03ms, 10.4MB)
테스트 4 〉	통과 (0.05ms, 10.1MB)
테스트 5 〉	통과 (0.04ms, 10.4MB)
테스트 6 〉	통과 (0.07ms, 10.3MB)
테스트 7 〉	통과 (0.12ms, 10.3MB)
테스트 8 〉	통과 (0.03ms, 10.3MB)

• 고수의 풀이. 뭔지 모르겠다 ㅋㅋㅋ

import heapq as hq

def solution(n, costs):
    answer = 0
    from_to = list(list() for _ in range(n))
    visited = [False] * n
    priority = []

    for a, b, cost in costs:
        from_to[a].append((b, cost))
        from_to[b].append((a, cost))

    hq.heappush(priority, (0, 0))
    while False in visited:
        cost, start = hq.heappop(priority)
        if visited[start]: continue

        visited[start] = True
        answer += cost
        for end, cost in from_to[start]:
            if visited[end] : continue
            else:
                hq.heappush(priority, (cost, end))

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.3MB)
테스트 4 〉	통과 (0.06ms, 10.4MB)
테스트 5 〉	통과 (0.02ms, 10MB)
테스트 6 〉	통과 (0.11ms, 10.4MB)
테스트 7 〉	통과 (0.05ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.3MB)

• 그나마 이쪽이 좀 더 이해가 쉽다.
  • 나랑 비슷한 거 같은데, Visited랑 sortedCost를 지우면서 하는데도 빠르네...

def solution(n, costs):
    answer = 0

    V = set()
    for v1, v2, cost in costs:
        V.add(v1)
        V.add(v2)
    sortedCosts = sorted(costs, key = lambda x: x[2])

    visited = set()

    visited.add(V.pop())
    while V:
        for i in range(len(sortedCosts)):
            v1, v2, cost = sortedCosts[i]
            if v1 in visited and v2 in visited:
                sortedCosts.pop(i)
                break
            elif v1 in visited or v2 in visited:
                if v1 in V:
                    V.remove(v1)
                if v2 in V:
                    V.remove(v2)
                visited.add(v1)
                visited.add(v2)
                answer += cost
                sortedCosts.pop(i)
                break

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.05ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.4MB)
테스트 6 〉	통과 (0.03ms, 10.2MB)
테스트 7 〉	통과 (0.05ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.2MB)

• 내 문제점이 뭔가 길찾기나 지도나 그래프 문제 나오면 2차원 배열부터 그릴려고 해서 시간을 낭비하는 것 같다.
  • 고칠점인 듯...