문제 설명

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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

풀이

간만에 아무 도움도 받지않고 혼자 힘으로 푼 문제라 뿌듯하다.

from math import inf


def solution(n, costs):
    answer = 0
    Map = [[inf for _ in range(n)] for _ in range(n)]
    for i in range(n):
        Map[i][i] = 0
    for cost in costs:
        Map[cost[0]][cost[1]] = cost[2]
        Map[cost[1]][cost[0]] = cost[2]

    costs_sorted = sorted(costs, key=lambda x: x[2])
    first = costs_sorted.pop(0)
    visited = [0] * n
    visited[first[0]] = 1
    visited[first[1]] = 1
    answer += first[2]
    while 1:
        Min = inf
        Min_idx = 0
        if visited.count(1) == n:
            break
        for i in range(len(Map)):
            if visited[i] == 0: # 아직 방문 안 했으면 패스(방문한 노드들에서 가장 가까운 것을 봐야하므로)
                continue
            for j in range(len(Map[0])):
                if visited[j] == 1: #방문 했으면 패스(중복을 피하려고)
                    continue
                if Map[i][j] <= Min and Map[i][j] != 0:
                    Min_idx = j
                    Min = Map[i][j]

        visited[Min_idx] = 1
        answer += Min
    return answer

우선 맵을 만들어주고
코스트 값들을 넣어주고 자기 자신은 0으로, 연결되지 않은 부분은 inf로 초기화시켜준다.

그런 다음 코스트 리스트를 코스트값으로 정렬시키고 가장 첫번째 값을 first로 받아온다.

visited 리스트를 만들고
first[0]과 first[1] 을 체크해준다.

answer 에다가 first[2]를 추가해주고
while문을 돌린다.

while문 안에서는 Map을 돌면서 방문했던 노드들에서 가장 인접한, 즉 코스트 값이 가장 작은 것을 기억하고(이때, 자기 자신을 나타내는 0과 이미 방문한 노드들을 걸러야함)
노드를 Min_idx에 그 노드까지 가는 코스트를 Min에다가 계속 갱신한다.

for문을 다 돌고 나오면 방문을 체크해주고 Min값을 answer에 추가해준다.

그리고 방문리스트를 검사해서
모두 방문했으면 while문 빠져나온다.

알고리즘 수업시간에 비슷한 문제를 배웠던 기억이나서
기억나는대로 풀었더니 풀렸다!!