[프로그래머스]지형 이동

[61] 지형 이동

책 구매하기

문제 정보

• 분류: 정렬
• 정답률: 14%
• 권장 시간 복잡도: O(N^2 log N)
• 핵심 키워드: 영역 나누기, MST, 유니온 파인드, 최소 사다리 비용
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/62050

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

높이 차가 threshold 이하인 칸은 같은 영역으로 묶을 수 있고, 그 이후에는 영역끼리 최소 비용으로 연결하면 된다. 결국 '영역 분할 + 영역 그래프의 MST'로 바뀌는 문제다.

정렬 문제는 손이 바빠지기 전에 비교 기준부터 정리하는 게 먼저다. 어떤 값을 기준으로 한 번만 정렬하면 그다음 오히려 짧아지는 경우가 많다.

풀이 흐름

1. BFS로 이동 가능한 칸들을 묶어 영역 번호를 만든다.
2. 서로 다른 영역이 맞닿은 경계에서 최소 높이 차를 간선으로 모은다.
3. 간선을 비용순으로 정렬해 Kruskal로 전체 영역을 연결한다.

구현할 때 놓치기 쉬운 부분

높이 차가 기준 이하인 칸은 같은 영역으로 묶을 수 있다. 그다음에는 영역끼리 연결하는 비용을 최소로 만들어야 하므로 영역화와 최소 신장 트리 관점을 같이 써야 한다.

파이썬 정답 코드

from collections import deque

def solution(land, height):
  # BFS로 이동 가능한 칸들을 묶어 영역 번호를 만든다.
  n = len(land)
  group = [[-1] * n for _ in range(n)]
  group_count = 0

  # 서로 다른 영역이 맞닿은 경계에서 최소 높이 차를 간선으로 모은다.
  for r in range(n):
    for c in range(n):
      if group[r][c] != -1:
        continue

      q = deque([(r, c)])
      group[r][c] = group_count

      while q:
        x, y = q.popleft()
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
          nx, ny = x + dx, y + dy
          if 0 <= nx < n and 0 <= ny < n and group[nx][ny] == -1:
            if abs(land[x][y] - land[nx][ny]) <= height:
              group[nx][ny] = group_count
              q.append((nx, ny))

      group_count += 1

  edge_cost = {}
  # 간선을 비용순으로 정렬해 Kruskal로 전체 영역을 연결한다.
  for r in range(n):
    for c in range(n):
      for dr, dc in ((1, 0), (0, 1)):
        nr, nc = r + dr, c + dc
        if not (0 <= nr < n and 0 <= nc < n):
          continue
        a = group[r][c]
        b = group[nr][nc]
        if a == b:
          continue
        cost = abs(land[r][c] - land[nr][nc])
        key = (min(a, b), max(a, b))
        if key not in edge_cost or cost < edge_cost[key]:
          edge_cost[key] = cost

  edges = sorted((cost, a, b) for (a, b), cost in edge_cost.items())
  parent = list(range(group_count))

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

  answer = 0
  for cost, a, b in edges:
    ra = find(a)
    rb = find(b)
    if ra == rb:
      continue
    parent[rb] = ra
    answer += cost

  return answer

시간 복잡도

N은 land의 한 변 길이이다.

전체 상태 수를 N^2개 수준으로 보고, 각 상태를 처리할 때 힙이나 분할 단계 때문에 로그 비용이 더 붙는다. 그래서 N^2개의 상태 처리 비용에 log N이 곱해진다.

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