---

문제 링크

문제 링크

---

< 문제 이해 >

• n개의 섬이 존재 - 섬 사이는 다리로 연결 ( 비용 : 다리 건설 비용 )
• 최소의 비용으로 모든 섬이 통행이 가능하도록 하기!
  • 다리를 여러번 건너 목적지에 도달할 수 있다면 통행가능으로 간주
    • A - B , B - C 있다면 ⇒ A - C 가능
• costs
  • 0 → 출발 섬
  • 1 → 도착 섬
  • 2 → 두 섬 연결하는 다리 건설 비용
• return → 최소 비용

---

< 문제 핵심 >

1. Kruskal 이용

   • 모든 정점, 최소비용

2. 최소 비용을 찾기

   • 비용을 기준으로 오름차순 정렬하기

3. 방문한 섬 체크

   • routes 배열 생성하여 방문한 섬을 넣기

4. 최종 비용

   • answer에 가중치를 더해서 최종 비용을 return

---

< 문제 아이디어 >

• 크루스칼 알고리즘

---

< 코드 >

1. 크루스칼 알고리즘

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x:x[2])
    routes = set([costs[0][0]])
    while len(routes) != n :
        for idx,cost in enumerate(costs) :
            if cost[0] in routes and cost[1] in routes :
                continue
            if cost[0] in routes or cost[1] in routes :
                routes.update([cost[0],cost[1]])
                answer+= cost[2]
                costs[idx] = [-1,-1,-1]
                break
    return answer

---

< 구현 방식 >

( 사용한 메소드, 라이브러리 등 원리 )

1. Kruskal 이용

• 섬 연결하기는 크루스칼의 가장 기본적인 문제?입니다
• 크루스칼은 탐욕적인 방법을 이용하여 네트워크의 모든 정점을 최소의 비용으로 연결하여 최적의 해답을 구하는 알고리즘입니다.
• 모든 정점, 최소비용

2. 최소 비용을 찾기

• costs[2]을 기준으로 오름차순 정렬하기

costs.sort( key= lambda x:x[2] )

3. 방문한 섬 체크

• routes는 방문한 섬들 체크하기 위해서
  • set([costs[0][0]) : 출발섬부터 담기
    • set 사용하는 이유는 중복을 제거하기 위해서입니다.
• for문
  • routes안에 출발섬, 도착섬이 이미 존재하면 방문한 섬이므로 넘어가기
  • 두 섬 중 한개의 섬이 방문한 섬이 아닐 경우
    • update 처리로 routes에 출발섬 A, 도착섬 B을 넣어준다
    • 하나는 이미 방문한 섬이지만 set이 중복을 자동 처리시켜준다.
    • A - B 를 연결하는 다리의 비용을 answer에 더하기
    • 검사한 곳은 [-1,-1,-1] 로 처리해주기

4. 최종 비용

• answer에 가중치를 더해서 최종 비용을 return

---

< 결과 >

1. 크루스칼 사용