[프로그래머스]경주로 건설

[45] 경주로 건설

책 구매하기

문제 정보

• 분류: 그래프
• 정답률: 43%
• 권장 시간 복잡도: O(N^2 log(N^2))
• 핵심 키워드: 방향 상태, 최소 비용, 우선순위 큐, 코너 비용
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/67259

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

같은 칸이라도 어떤 방향으로 들어왔는지가 비용을 바꾼다. 그래서 좌표만 방문 체크하면 안 되고, 좌표+방향을 하나의 상태로 봐야 한다.

최단 거리나 연결성처럼 칸과 칸, 정점과 정점 사이를 따라가야 하는 문제는 결국 탐색 구조가 핵심이다. 방문 상태를 어떻게 정의하느냐가 정답을 거의 결정한다.

풀이 흐름

1. 상태를 (행, 열, 방향)으로 잡는다.
2. 직진은 100, 코너는 600 비용을 더한다.
3. 우선순위 큐로 최소 비용 상태부터 꺼내며 도착점의 최소값을 찾는다.

구현할 때 놓치기 쉬운 부분

같은 칸에 도착하더라도 들어온 방향이 다르면 이후 비용이 달라진다. 좌표만 방문 처리하면 더 비싼 경로와 더 싼 경로를 구분할 수 없어 정답이 무너진다.

파이썬 정답 코드

import heapq

def solution(board):
  # 상태를 (행, 열, 방향)으로 잡는다.
  n = len(board)
  INF = 10 ** 15
  cost = [[[INF] * 4 for _ in range(n)] for _ in range(n)]
  heap = []

  # 직진은 100, 코너는 600 비용을 더한다.
  for d, (dr, dc) in enumerate(((1, 0), (-1, 0), (0, 1), (0, -1))):
    nr, nc = dr, dc
    if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0:
      cost[nr][nc][d] = 100
      heapq.heappush(heap, (100, nr, nc, d))

  # 우선순위 큐로 최소 비용 상태부터 꺼내며 도착점의 최소값을 찾는다.
  while heap:
    cur_cost, r, c, d = heapq.heappop(heap)
    if cur_cost > cost[r][c][d]:
      continue

    for nd, (dr, dc) in enumerate(((1, 0), (-1, 0), (0, 1), (0, -1))):
      nr, nc = r + dr, c + dc
      if not (0 <= nr < n and 0 <= nc < n):
        continue
      if board[nr][nc] == 1:
        continue

      extra = 100 if d == nd else 600
      next_cost = cur_cost + extra

      if next_cost < cost[nr][nc][nd]:
        cost[nr][nc][nd] = next_cost
        heapq.heappush(heap, (next_cost, nr, nc, nd))

  return min(cost[n - 1][n - 1])

시간 복잡도

N은 board의 한 변 길이이다.

격자 칸을 상태로 보면 상태 수가 N^2개이다. 여기에 우선순위 큐 정렬 비용이 붙어 각 삽입·삭제마다 log(N^2)이 걸리므로 전체가 O(N^2 log(N^2))이 된다.

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