📌 문제 설명

경주로 건설 문제 보기

📌 문제 접근

가중치(비용)가 다를 때의 최단 거리 탐색

단순히 거리가 1씩 늘어나는 것이 아니라 직선(100)과 코너(600)처럼 비용이 다를 때는, 개인적으로 우선순위 큐(다익스트라)를 직접 구현해서 푸는 것을 선호한다. 눈에 익은 코드라 디버깅이 훨씬 수월하기 때문이다. 물론 자바스크립트는 내장된 힙(Heap) 라이브러리가 없어 생짜로 구현하는 데 시간이 좀 걸린다. 게다가 이 문제는 맵 크기 제한이 최대 25x25 (625칸) 밖에 안 돼서 일반 큐(Queue)를 써도 무방하지만, 알고리즘 최적화 연습 겸 나만의 확실한 풀이법을 적용해 보았다.

3차원 상태 관리를 통한 비용 계산

이전 칸에서 어느 방향으로 들어왔는지에 따라 다음 코너 비용이 달라진다. 이를 해결하기 위해 visited 배열에 방향(z축)을 추가하여 3차원 배열로 상태를 관리했다. 최적화를 위해 해당 칸·해당 방향으로 진입할 때의 최소 누적 비용을 함께 저장하며 BFS 탐색을 진행했다.

📌 내가 작성한 코드

class MinHeap {
  constructor() {
    this.heap = [];
  }
  size() {
    return this.heap.length;
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
  push(data) {
    this.heap.push(data);
    this.bubbleUp();
  }
  bubbleUp() {
    let idx = this.size() - 1;
    while (idx) {
      const parent_idx = ~~((idx - 1) / 2);
      if (this.heap[parent_idx][3] > this.heap[idx][3]) {
        this.swap(parent_idx, idx);
        idx = parent_idx;
      } else break;
    }
  }
  pop() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();
    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return top;
  }
  bubbleDown() {
    let idx = 0;
    const len = this.size();
    let [left_idx, right_idx] = [idx * 2 + 1, idx * 2 + 2];
    while (true) {
      let [left_idx, right_idx] = [idx * 2 + 1, idx * 2 + 2];
      if (left_idx >= len) break;
      let s = idx;
      if (left_idx < len && this.heap[left_idx][3] < this.heap[s][3])
        s = left_idx;
      if (right_idx < len && this.heap[right_idx][3] < this.heap[s][3])
        s = right_idx;
      if (s === idx) break;
      this.swap(s, idx);
      idx = s;
    }
  }
}

function solution(board) {
  const n = board.length;
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];

  const heap = new MinHeap();
  const visited = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => [Infinity, Infinity]),
  );
  visited[0][0][0] = 0;
  visited[0][0][1] = 0;

  heap.push([0, 0, 0, 0]);
  heap.push([0, 0, 1, 0]);

  while (heap.size()) {
    const [x, y, z, cnt] = heap.pop();
    if (visited[x][y][z] < cnt) continue;
    if (x === n - 1 && y === n - 1) return cnt * 100;
    for (let l = 0; l < 4; l++) {
      const nx = x + dx[l];
      const ny = y + dy[l];
      if (0 <= nx && nx < n && 0 <= ny && ny < n && !board[nx][ny]) {
        const nz = l === 0 || l === 1 ? 0 : 1;
        const ncnt = z === nz ? 1 + cnt : 6 + cnt;
        if (visited[nx][ny][nz] < ncnt) continue;
        visited[nx][ny][nz] = ncnt;
        heap.push([nx, ny, nz, ncnt]);
      }
    }
  }
  return;
}

📌 시간 복잡도

• 각 칸을 방향 2개 상태로 관리하고, 우선순위 큐를 사용한 다익스트라 방식으로 탐색하므로 전체 시간 복잡도는 O(N^2 log N)

📌 참고 링크

• 구조분해할당

• 다익스트라 알고리즘