[프로그래머스] 섬 연결하기

문제 링크

---

프로그래머스

 

접근

---

1) 플로이드 워셜 - 실패

• 처음엔 모든 노드 간 최단 거리를 알아야 한다고 생각되어 플로이드 워셜로 접근하고, costs를 다시 탐색하면서 갱신된 테이블과 값이 일치할 경우에 result에 더하는 방식으로 접근했다. 하지만 이럴 경우 사이클이 있을 때 중복되어 값이 더해지는 경우가 발생한다.
• 아래와 같은 그래프가 있을 때 모든 노드를 연결하기 위한 경로는 빨간색 동그라미인 1, 2만 있으면 된다. 하지만 위와 같이 접근하면 3으로 접근하는 경로도 3으로 주어져있기 때문에 더해지게 되므로 오답이 나게된다.

 

 

2) 크루스칼

def solution(n, costs):
    answer = 0
    sorted_cost = sorted(costs, key=lambda x: x[2])
    connect = {costs[0][0]}

    while len(connect) != n:
        for cost in sorted_cost:
            if cost[0] in connect and cost[1] in connect: # 양쪽 다 connection에 존재하면 skip
                continue
            if cost[0] in connect or cost[1] in connect: # 한쪽만 있을 경우에만 add
                connect.update([cost[0], cost[1]])
                answer += cost[2]
                sorted_cost.remove(cost)
                break

    return answer

• 거리 기준 오름차순으로 우선 sorting을 하고, 현재 connect set과 연결 시 한 쪽만 연결될 경우에는 사이클이 형성되지 않으므로 추가하는 방식으로 접근한다. 두 쪽 다 연결된다는 것은 사이클이 있다는 것을 의미하므로 skip한다.
• 첫 번째 조건문에서 사실 cost[0], cost[1]이 connect에 존재하면, 해당 간선은 이후에 탐색할 필요 없기 때문에 제거해도 된다. 하지만 위처럼 sorted_cost를 대상으로 for를 돌리고 있기 때문에 예상치 못한 결과(탐색 안한 cost를 건너뛰는 경우 등)가 발생하므로 주의해야 한다. 그냥 skip해도 좋다.

 

 

그림으로 설명하면 다음과 같다.

• 2 - 3 - 4 - 5가 청록색 간선으로 이미 연결되어있다고 하자. 이는 하나의 Set(2, 3, 4, 5)를 의미한다.
• 해당 간선을 추가하면 사이클이 형성되기 때문에 skip한다. 또한 이미 짧은 간선부터 처리가 되었기 때문에 해당 간선은 쓸모가 없다.