코딩테스트를 위한 JavaScript 알고리즘

bfs

start - [x, y, time]
end - [x, y]
board - 이차원 배열 (O - 이동 가능 / X - 불가능)
visited - 방문 기록 (방문 확인 1 / 미방문 0)

start에서 end까지 가는 시간 계산
시작시간은 start의 세번째 인자 기준으로 도달하지 못하는 경우 -1

const bfs = (start, end, board) => {
    const dx = [-1, 1, 0, 0]
    const dy = [0, 0, -1, 1]
    const visited = Array.from({ length: board.length }, () => Array(board[0].length).fill(0))
    visited[start[0]][start[1]] = 1
    const queue = [start]

    while (queue.length) {
        const [x, y, time] = queue.shift()
        for (let i = 0; i < 4; i++) {
            const [nx, ny] = [x + dx[i], y + dy[i]]
            if (0 <= nx && nx < board.length &&
                0 <= ny && ny < board[0].length &&
                !visited[nx][ny] &&
                board[nx][ny] !== 'X'
               ) {
                       if (nx === end[0] && ny === end[1]) {
                        return time + 1
                    }
                    queue.push([nx, ny, time + 1])
                    visited[nx][ny] = 1
            }
        }
    }
    return -1
}

dfs

const dfs = (x, y, time, end, board, visited) => {
    if (x === end[0] && y === end[1]) return time

    for (let i = 0 i < 4 i++) {
        const [nx, ny] = [x + dx[i], y + dy[i]]
        if (
            0 <= nx && nx < board.length &&
            0 <= ny && ny < board[0].length &&
            !visited[nx][ny] &&
            board[nx][ny] !== 'X'
        ) {
            visited[nx][ny] = 1
            const result = dfs(nx, ny, time + 1, end, board, visited)
            if (result !== -1) {
                return result
            }
            visited[nx][ny] = 0
        }
    }

    return -1
}

const solveDFS = (start, end, board) => {
    const dx = [-1, 1, 0, 0]
    const dy = [0, 0, -1, 1]
    const visited = Array.from({ length: board.length }, () => Array(board[0].length).fill(0))
    visited[start[0]][start[1]] = 1

    return dfs(start[0], start[1], 0, end, board, visited)
}

최대 힙 (우선순위 큐, heap)

class MaxHeap {
  constructor() {
    this.heap = [];
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
  }

  heapifyUp(index) {
    let currentIndex = index;
    let parentIndex = this.getParentIndex(currentIndex);

    while (currentIndex > 0 && this.heap[currentIndex] > this.heap[parentIndex]) {
      this.swap(currentIndex, parentIndex);
      currentIndex = parentIndex;
      parentIndex = this.getParentIndex(currentIndex);
    }
  }

  extractMax() {
    if (this.heap.length === 0) return null;

    const max = this.heap[0];
    const end = this.heap.pop();

    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.heapifyDown(0);
    }

    return max;
  }

  heapifyDown(index) {
    let largest = index;
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);

    if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[largest]) {
      largest = leftChildIndex;
    }

    if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[largest]) {
      largest = rightChildIndex;
    }

    if (largest !== index) {
      this.swap(index, largest);
      this.heapifyDown(largest);
    }
  }

  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  size() {
    return this.heap.length;
  }
}

최소 힙

class MinHeap {
  constructor() {
    this.heap = [];
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
  }

  heapifyUp(index) {
    let currentIndex = index;
    let parentIndex = this.getParentIndex(currentIndex);

    while (currentIndex > 0 && this.heap[currentIndex] < this.heap[parentIndex]) {
      this.swap(currentIndex, parentIndex);
      currentIndex = parentIndex;
      parentIndex = this.getParentIndex(currentIndex);
    }
  }

  extractMin() {
    if (this.heap.length === 0) return null;

    const min = this.heap[0];
    const end = this.heap.pop();

    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.heapifyDown(0);
    }

    return min;
  }

  heapifyDown(index) {
    let smallest = index;
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);

    if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[smallest]) {
      smallest = leftChildIndex;
    }

    if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallest]) {
      smallest = rightChildIndex;
    }

    if (smallest !== index) {
      this.swap(index, smallest);
      this.heapifyDown(smallest);
    }
  }

  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  size() {
    return this.heap.length;
  }
}