[프로그래머스][greedy] 섬연결하기(201015)

1. 문제 설명 

 

https://programmers.co.kr/learn/courses/30/lessons/42861

 

코딩테스트 연습 - 섬 연결하기

\

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

입출력 예

ncosts                                                  return

4

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

4

 

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며,

이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

 

 

 

 

 

 

2. 풀이 

이렇게 각 노드, 가중치를 주고 각 노드들을 다 이어주는 최소 가중치 경로를 찾는 문제를 최소 신장트리 MST 라 부른다. 

그리고 여기에는 크루스칼, 프림 2가지 알고리즘 풀이 법이 있다.

 

크루스칼 알고리즘

- 노드를 모두 연결하는 최소 비용의 간선을 파악 

- 따라서 가중치가 작은 간선부터 탐색하도록 정렬 

- 만약 이미 경로가 되어있는 곳에서 사이클이 만들어질 경우 그 간선은 선택하지 않음 

- DFS, BFS 를 통해 이미 사이클이 만들어 졌는지 아닌지를 필히 확인해야함 

 

프림 알고리즘

- 현위치에서 가중치가 낮은 간선부터 연결시킴 

- 그러나 트리를 처음부터 끝까지 유지시킴 

 

최소 신장 트리 (MST, 크루스칼, 프림 알고리즘)

mini-ko.tistory.com/8

최소비용신장트리(MST), 크루스칼, 프림 알고리즘

 

1) 처음 시도 - 사이클이 만들어 지는 경우를 제외하지 못함 

def solution(n, costs):
    path_dict = {}

    sor_costs = sorted(costs, key=lambda x: x[2])

    for one_cost in sor_costs:
        st, end, cost = one_cost[0], one_cost[1], one_cost[2]
        if end not in path_dict.keys():
            path_dict[end] = cost

    return sum(path_dict.values())

 

 

2) 2차 시도 (성공) - 크루스칼 알고리즘으로 풀기 

def solution(n, costs):

    path_chk_list = [0] * n
    sor_costs = sorted(costs, key = lambda x:x[2])
    
    total_cost, path_move = 0, 0
    path_chk_list[0] = 1 # start point
    
    while path_move != n-1:
        for one_cost in sor_costs:
            st, end, cost = one_cost[0], one_cost[1], one_cost[2]
            if (path_chk_list[st] + path_chk_list[end]) == 1 :
                path_chk_list[st] = 1
                path_chk_list[end] = 1
                total_cost += cost
                path_move +=1
                break

    return total_cost

 

1/ path_chk_list 로 섬에 방문했는지  체크한다

2/ sor_cost --> 크루스칼로 풀기 때문에 cost를 오름차순으로 정렬한다. (설치값 작은게 앞으로 나오도록) 

3/ total_cost 에 총 설치 비용이 담기고, path move 는 몇번 설치 했는지를 체크하는 값이다 

4/ 전체를 while 로 돌리는데 이때 설치가 n-1 번 되는 순간 스톱 (섬이 n 개면 그 사이 길은 n-1 개 이하만 세울 수 있으니까 !) 

5/ 정렬된 정보를 하나씩 꺼내는데, 

 --> 만약 시작점, 끝점 둘중 하나만 1인 경우 (다음 경로를 찾는 상황임) 

     --> 비용 더해주고 해당 비용 총 비용에 더해주고, 끝냄 

                  *** 왜냐면, 코스트 정렬해서 들어왔기 때문에 해당 지점에서 나아갈 다음 경로중

                                   가장 최소의 비용으로 나아가는 연결지점일테니까 ==> 이게 중요함 ! 

 

6/ 그렇게 전부다 탐색하면 while문 끝나고, 토탈 비용 반환 

 

 

 

3. 정리

아직 크루스칼, 프림 감이 잘 안오는데 내일 유사한 문제를 더 풀어봐야겠담 !