Programmers / Level 3 / 경주로 건설 / JS

https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

 

문제분석

직선도로에서는 100의 비용이 들고,

코너에서는 500의 비용이 든다.

처음에 헷갈려서 틀렸었는데, '코너를 만드는데 드는 비용'이 500이므로,

코너를 만들고 앞으로 한 칸 나아가려면 총 600의 비용이 든다.

 

또한, 어느 방향에서 왔는지에 따라 같은 칸이라도 비용이 다르게 들 수 있다.

따라서 일반적인 방문처리를 하는 bfs로는 풀이가 불가능하다.

 

풀이

const EMPTY = 0;
const WALL = 1;

const STRAIGHT_COST = 100;
// 코너를 건설하는 값 + 앞으로 한 칸 나아가는 값
const CORNER_COST = 500 + STRAIGHT_COST;

// 상, 우, 하, 좌
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

let N;

function isValid(row, col) {
  return 0 <= row && row < N && 0 <= col && col < N;
}

function bfs(board) {
  // [행, 열, 방향, 금액]
  const queue = [];
  const visited = Array.from({ length: N }, () =>
    Array.from({ length: N }, () => Array(4).fill(Infinity))
  );

  if (board[1][0] === EMPTY) {
    queue.push([1, 0, 2, STRAIGHT_COST]);
    visited[1][0][2] = STRAIGHT_COST;
  }
  if (board[0][1] === EMPTY) {
    queue.push([0, 1, 1, STRAIGHT_COST]);
    visited[0][1][1] = STRAIGHT_COST;
  }

  while (queue.length > 0) {
    const [curRow, curCol, curDir, curCost] = queue.shift();

    for (let d = 0; d < 4; d++) {
      const nr = curRow + dr[d];
      const nc = curCol + dc[d];

      // 배열 범위를 벗어날 경우 스킵한다.
      if (!isValid(nr, nc)) {
        continue;
      }
      // 벽일 경우 스킵한다.
      if (board[nr][nc] === WALL) {
        continue;
      }

      // 이전과 다른 방향일 경우, 코너이기 때문에 비용이 증가한다.
      const newCost =
        curDir === d ? curCost + STRAIGHT_COST : curCost + CORNER_COST;

      // 이미 더 적은 비용으로 방문한적이 있다면 스킵한다.
      if (visited[nr][nc][d] <= newCost) {
        continue;
      }

      visited[nr][nc][d] = newCost;
      queue.push([nr, nc, d, newCost]);
    }
  }

  let minCost = Math.min(...visited[N - 1][N - 1]);
  return minCost;
}

function solution(board) {
  N = board.length;

  let minCost = bfs(board);
  return minCost;
}

 

`isValid(row, col)`

function isValid(row, col) {
  return 0 <= row && row < N && 0 <= col && col < N;
}

현재 있는 행 또는 열이 배열의 범위를 벗어나지 않았는지 판단하는 함수이다.

 

`bfs(board)`

function bfs(board) {
  // [행, 열, 방향, 금액]
  const queue = [];
  const visited = Array.from({ length: N }, () =>
    Array.from({ length: N }, () => Array(4).fill(Infinity))
  );

  if (board[1][0] === EMPTY) {
    queue.push([1, 0, 2, STRAIGHT_COST]);
    visited[1][0][2] = STRAIGHT_COST;
  }
  if (board[0][1] === EMPTY) {
    queue.push([0, 1, 1, STRAIGHT_COST]);
    visited[0][1][1] = STRAIGHT_COST;
  }

  while (queue.length > 0) {
    const [curRow, curCol, curDir, curCost] = queue.shift();

    for (let d = 0; d < 4; d++) {
      const nr = curRow + dr[d];
      const nc = curCol + dc[d];

      // 배열 범위를 벗어날 경우 스킵한다.
      if (!isValid(nr, nc)) {
        continue;
      }
      // 벽일 경우 스킵한다.
      if (board[nr][nc] === WALL) {
        continue;
      }

      // 이전과 다른 방향일 경우, 코너이기 때문에 비용이 증가한다.
      const newCost =
        curDir === d ? curCost + STRAIGHT_COST : curCost + CORNER_COST;

      // 이미 더 적은 비용으로 방문한적이 있다면 스킵한다.
      if (visited[nr][nc][d] <= newCost) {
        continue;
      }

      visited[nr][nc][d] = newCost;
      queue.push([nr, nc, d, newCost]);
    }
  }

  let minCost = Math.min(...visited[N - 1][N - 1]);
  return minCost;
}

bfs로 얻은 결과를 반환해주는 함수이다.

코드가 한 번에 보기 어려우므로 쪼개서 살펴보자.

 

// [행, 열, 방향, 금액]
const queue = [];

bfs의 기본 시작은 큐를 만들어주고, 방문 처리할 배열을 만들어주는 것이다.

큐에는 [행, 열, 방향, 금액]을 넣어준다.

 

여기서 방향은 간단히 방향 배열의 인덱스로 판단해준다. 

(상: 0, 우: 1, 하: 2, 좌: 3)

// 상, 우, 하, 좌
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

 

const visited = Array.from({ length: N }, () =>
  Array.from({ length: N }, () => Array(4).fill(Infinity))
);

다만, 여기서 방문 처리할 배열은 기본 2차원이 아닌 3차원으로 만들어준다.

현재 칸에 도달하면, 몇 번의 코너를 거쳤는지에 따라 총 가격이 다르게 된다.

따라서 현재 칸의 어느 방향에서 왔는지를 각 4칸(상, 우, 하, 좌)에 저장해주는 것이다.

 

  if (board[1][0] === EMPTY) {
    queue.push([1, 0, 2, STRAIGHT_COST]);
    visited[1][0][2] = STRAIGHT_COST;
  }
  if (board[0][1] === EMPTY) {
    queue.push([0, 1, 1, STRAIGHT_COST]);
    visited[0][1][1] = STRAIGHT_COST;
  }

다음으로, 첫 시작을 넣어준다.

처음 시작은 무조건 [0][0]에서 한다고 문제에 나와있다.

그러면, 다음으로 갈 수 있는 칸은 바로 아래 칸이나 오른쪽 칸이다.

무조건 갈 수 있는건 아니고,

해당 칸이 벽으로 막혀있지 않은지, 즉 빈 칸인 경우에만 큐에 넣어주고 방문처리를 해준다.

 

  while (queue.length > 0) {
    const [curRow, curCol, curDir, curCost] = queue.shift();

    for (let d = 0; d < 4; d++) {
      const nr = curRow + dr[d];
      const nc = curCol + dc[d];

      // 배열 범위를 벗어날 경우 스킵한다.
      if (!isValid(nr, nc)) {
        continue;
      }
      // 벽일 경우 스킵한다.
      if (board[nr][nc] === WALL) {
        continue;
      }

      // 이전과 다른 방향일 경우, 코너이기 때문에 비용이 증가한다.
      const newCost =
        curDir === d ? curCost + STRAIGHT_COST : curCost + CORNER_COST;

      // 이미 더 적은 비용으로 방문한적이 있다면 스킵한다.
      if (visited[nr][nc][d] <= newCost) {
        continue;
      }

      visited[nr][nc][d] = newCost;
      queue.push([nr, nc, d, newCost]);
    }
  }

bfs의 핵심 로직이다.

다른건 다 같지만, 마지막 조건 검사 부분이 일반적인 bfs와 다르다.

만약 현재 진행중이던 방향과 다른 방향이라면,

코너를 돌았다는 뜻이므로, 해당 경우에만 코너 값을 더해준다.

그리고 이미 더 적은 비용으로 방문한적이 있다면 스킵한다.

 

let minCost = Math.min(...visited[N - 1][N - 1]);

마지막으로, 도착지점의 4칸중에서 최소값을 찾아서 반환해주면 된다.