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

[37] 섬 연결하기

책 구매하기

문제 정보

• 분류: 집합
• 정답률: 45%
• 권장 시간 복잡도: O(E log E)
• 핵심 키워드: 크루스칼, 유니온 파인드, MST, 간선 정렬
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42861

문제를 읽을 때 체크할 포인트

모든 섬을 최소 비용으로 잇는 전형적인 최소 신장 트리 문제다. 간선을 비용순으로 정렬한 뒤, 사이클이 생기지 않는 간선만 고르는 크루스칼로 정리하면 된다.

연결 여부를 다시 계산하면 비효율이 커진다. 이미 같은 편인지 아닌지를 빠르게 확인할 수 있어야 하고, 그 지점에서 유니온 파인드가 바로 떠올라야 한다.

풀이 흐름

1. 간선을 비용 기준 오름차순으로 정렬한다.
2. 유니온 파인드로 두 정점이 이미 연결됐는지 확인한다.
3. 연결되지 않았다면 간선을 채택하고 union 하며 비용을 더한다.

구현할 때 놓치기 쉬운 부분

비용이 싼 간선부터 고르는 것만으로는 부족하다. 이미 같은 집합에 속한 정점을 다시 잇는 간선을 막아야 최소 신장 트리가 된다. 결국 비용 정렬과 사이클 방지가 같이 가야 한다.

파이썬 정답 코드

def solution(n, costs):
  # 간선을 비용 기준 오름차순으로 정렬한다.
  parent = list(range(n))

  def find(x):
    while parent[x] != x:
      parent[x] = parent[parent[x]]
      x = parent[x]
    return x

  def union(a, b):
    ra = find(a)
    rb = find(b)
    if ra == rb:
      return False
    parent[rb] = ra
    return True

  answer = 0
  # 유니온 파인드로 두 정점이 이미 연결됐는지 확인한다.
  for a, b, cost in sorted(costs, key=lambda x: x[2]):
    # 연결되지 않았다면 간선을 채택하고 union 하며 비용을 더한다.
    if union(a, b):
      answer += cost

  return answer

시간 복잡도

E는 간선 개수이다.

간선을 한 번 정렬하는 비용이 가장 크다. E개의 간선을 비용 기준으로 정렬하면 O(E log E)가 들고, 그 뒤 유니온 파인드로 채택 여부를 확인하는 부분은 거의 상수 시간으로 따라온다.

따라서 시간 복잡도는 O(E log E)이다.