[Programmers]섬 연결하기_Python

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/42861?language=python3

프로그래머스

 

문제

 

 

문제 해설

연결된 섬의 번호와 이동에 필요한 비용 list가 주어진다. 모든 섬을 지날 수 있는 최소비용을 반환하면 된다.

 

 

문제 풀이

해당 문제는 전체 노드를 방문할 수 있는 최소비용을 반환하는 문제로, 플로이드 와샬 알고리즘을 이용해서 풀었다.

먼저, 필요한 자원은
1. checked : 방문여부 체크
2. values : 해당 노드와 연결된 노드로부터, 해당 노드로 갈 수 있는 최소 비용 리스트. default = 99999로 최댓값으로 저장해놓는다.
3. graph : 문제에서 입력 받은 연결 노드 정보와 비용을 담을 dictionary

* 모든 노드를 방문할 때까지 아래 로직을 반복한다.

(1) 현재 노드(시작=0번 index)와 연결된 노드를 방문한 적이 없다면, 해당 노드 방문에 필요한 비용을 min(현재 저장된 비용, 현재노드 -> 연결노드 비용) 으로 갱신한다.

(2) 현재 방문하지 않은 노드 중, 최소 비용을 가진 노드를 탐색한 뒤, 최소비용을 answer에 더해준다.
  -  방문하지 않은 노드 중, 최소 비용의 노드는 반드시 방문해야 하는 노드이다.
(1)에서 현재 노드를 기준으로 최솟값으로 갱신해주었으니, 최소비용이 될 후보값들은 모두 이전에 방문한 노드들과 연결될 수 있는 노드들이다. 이 중에서 방문하지 않고 그 중에 최소비용을 가진 노드라면, 이번 타임에 필히 방문해야 하는 노드인 것이다.

(3) 해당 노드를 start로 갱신하고, 방문처리한다.

* 반복이 끝나면 answer을 반환한다.

 

 

* 코드

def solution(n, costs):
    checked = [False for _ in range(n)]
    values = [99999 for _ in range(n)]
    start = 0
    checked[start] = True
    values[start] = 0
    answer = 0
    graph = {}

    for i in range(len(costs)):
        new_key = costs[i][0]
        new_value = costs[i][1]

        updated_value = graph.get(new_key) or {}
        updated_value[new_value] = costs[i][2]
        graph[new_key] = updated_value

        updated_value = graph.get(new_value) or {}
        updated_value[new_key] = costs[i][2] 
        graph[new_value] = updated_value

    while False in checked:

        # 비용 최소값 갱신
        for i in graph[start]:
            if checked[i] == False:
                values[i] = min(values[i], graph[start][i])

        refer = 99999
        new_index = -1
        
        # 방문하지 않는 노드 중, 최소비용 노드 탐색
        for i in range(n):
            if checked[i] == False and values[i] != 0:
                if values[i] < refer:
                    refer = values[i]
                    new_index = i
        
        # 위에서 찾은 노드 방문처리 및 start 갱신
        answer = answer + refer
        checked[new_index] = True
        start = new_index

    return answer