[프로그래머스] LV.3 경주로 건설 (JS)

KG·2021년 5월 5일

알고리즘

목록 보기

42/61

문제

건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다.
제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다.
설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.
경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다.
경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽이 있는 칸에는 경주로를 건설할 수 없습니다.
이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 합니다.
또한 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.
건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 듭니다.
죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.

도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.

제한

board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
- 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
- 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

입출력 예시

board	result
[[0,0,0],[0,0,0],[0,0,0]]	900
[[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]]	3800
[[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]]	2100
[[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0]]	3200

풀이

2020 카카오 인턴십에서 출제된 문제이다. 최단 경로를 탐색하는 문제인데 직선 경로이냐 코너 경로이냐에 따라 매겨지는 소요 비용이 다르다는 조건이 추가되었다. 해당 조건을 잘 고려해서 BFS 알고리즘을 적용하여 풀어보도록 하자.

코너 vs 직선 경로 구분

직선 경로인지 코너 경로인지 구분하는 점만 제외한다면 일반적인 BFS 알고리즘으로 최단 경로를 구하는 문제와 동일한 포맷이다. 따라서 우리는 직선인지 코너인지를 구분하는 법을 추가로 구현해서 BFS 알고리즘을 작성하면 될 것 이다. 그렇다면 직선 경로인지 코너 경로인지 어떻게 구분할 수 있을까?

먼저 이동할 수 있는 공간이 존재하고, 벽이 없는 경우라면 자동차는 상하좌우 4가지 방향으로 이동할 수 있다. 보통의 경우엔 dx와 dy 등의 좌표를 두어 상하좌우의 이동경로를 계산해주지만 해당문제에서는 다른 방식으로 접근해보자.

그러기 위해서 먼저 직선경로인지 코너링인지 판단할 수 있는 조건이 마련되어야 한다. 이는 간단하게 구분할 수 있다. 만약 이전에 이동했던 방향과 현재 이동하는 방향이 일치한다면 직선경로이고 일치하지 않는다면 코너경로가 될 것이다.

이전 경로 === 현재 경로 : 직선경로
이전 경로 !== 현재 경로 : 코너경로

따라서 우리는 BFS 탐색을 돌릴 때 좌표값 뿐만 아니라 이전의 경로에 대한 정보 역시 저장해주어야 할 필요가 있다. 그리고 이전 경로와 다음에 이동할 경로를 비교하여 해당 방향이 직선 경로인지 아닌지를 판별할 수 있을 것 이다.

하나의 위치좌표에서 이동방향을 다음과 같이 정의해주자.

0 : 우향 ➡
1 : 하향 ⬇
2 : 좌향 ⬅
3 : 상향 ⬆

위와 같이 방향을 정해주었을 때, 이전의 경로와 현재 경로를 비교하여 직선경로인지 아닌지를 판별해주는 식을 짤 수 있다. 가장 중요한 것은 코너링이 가장 적은 최단경로를 구성해야 한다는 것이다. 즉 단순히 거리상으로 가장 짧은 경로를 구하는 것은 아니지만 최단 경로에 가까울 수록 정답일 확률이 높아진다. 따라서 우리는 이전에 진행한 방향의 역방향으로 진행하는 경우는 제외할 필요가 있다. 이는 사실 보통의 BFS 탐색에서 별도 visit 배열을 두어 방문여부를 체크하는 것과도 동일한 로직이다.

위에서 정한 방향값들을 자세히 보면 서로의 역방향에 해당하는 방향과 2만큼 차이가 발생하는 것을 알 수 있다. 따라서 우리는 상하좌우의 값을 dx 및 dy 를 통해 일일이 접근하지 않고 하나의 directions 배열을 선언하고 여기서 2를 제외한 [0, 1, 3]의 값으로 초기화하여 진행방향을 단순하게 계산해줄 수 있다. 이때 방향은 총 4가지 경우의 수밖에 없기 때문에 (이전경로 + 갈 수 있는 방향) % 4의 결과값을 다음의 방향으로 정할 수 있을 것이다. 지금까지의 내용을 정리하면 다음과 같다.

queue는 [Y좌표, X좌표, 현재방향, 현재위치까지의 건설비용]의 형태의 원소를 가져야 할 것이다.
- 현재방향 값을 통해 이전 경로와 비교 가능
- 건설비용을 저장해 최소비용이 나타나면 갱신해주어야 한다
directions = [0, 1, 3]으로 이전방향과 연산을 통해 다음에 나아갈 방향 결정

...

const directions = [0, 1, 3];

...

while(queue.length) {
  // 현재 자동차의 좌표 및 방향, 가격 정보
  const [Y, X, direction, price] = queue.shift();
  ...
  for(const dir of directions) {
    // (현재 방향 + 역방향 제외 방향값) % 4
    // 결과값은 역방향을 제외한 나머지 3방향이 된다.
    const direct = (direction + dir) % 4;
    ...
  }
}

이동방향 적용 함수

위에서 역방향을 제외한 방향값을 계산해주는 로직을 구성했다. BFS 함수 내부에서 이 방향을 적용한 위치좌표를 계산해줄 수 있겠지만 가독성을 위해 외부에 함수로 따로 구현해주자. 반환할 수 있는 방향은 총 4개가 될 것이며, 위에서 언급한대로 각 방향은 0: 우향, 1: 하향, 2: 좌향, 3: 상향이다. 이에 맞춰 좌표값을 리턴해주도록 구현하면 된다.

const getDirection = (Y, X, dir) => {
  if(dir === 0) return [Y, X+1];
  else if(dir === 1) return [Y+1, X];
  else if(dir === 2) return [Y, X-1];
  else return [Y-1, X];
}

BFS 탐색을 통한 최소 건설 비용

다음은 최단 경로를 탐색하기 위한 BFS 알고리즘을 구현하자. BFS 반복문 내부에서 이동가능한 경로 범위를 계산해줄 수 있지만, 주어진 board 크기보다 1이 더 큰 테두리를 적용한 새로운 배열 new_board를 생성해주면 따로 범위 계산을 해 줄 필요는 없다. 이 부분은 각자의 편의에 따라 더 익숙하고 편한쪽으로 구현하면 되겠다. 굳이 장단점을 따지면 해당 방법의 경우는 별도로 이동가능 범위 계산에 대한 부분을 신경쓰지 않아도 되지만, 원본 배열에 비해 크기가 늘어나기에 공간복잡도가 더 커질 수 있다. 그런데 보통 코딩테스트에서 이 정도의 시간 또는 공간복잡도는 통과에 별 영향을 끼치지 않는다. 다른 방법이 궁금한 경우 해당 포스트에서 isMovable 함수를 참고하자.

또한 방문여부를 체크할 별도의 배열은 선언해주지 않아도 상관없다. 위에서 역방향을 제외해주었기 때문에 무한루프에 빠질 일은 없다. 그러나 이미 방문한 경로를 다시 방문하는 경우는 생길 수 있다. 이는 의도된 것인데, 최단 경로가 항상 최소 비용임을 보장할 수 없기 때문이다. 따라서 갈 수 있는 공간은 이미 방문을 했더라도 각각의 방향으로 다시 접근하여 새로운 비용을 계산하여 기존 비용보다 저렴하다면 이를 갱신해주어야 한다. 따라서 위에서 생성한 new_board와 동일한 크기로 각 좌표의 건설 비용을 저장해 줄 costs 배열 역시 생성해주자. 만약 현재 좌표의 건설 비용보다 costs에 저장된 비용이 더 큰 경우 이를 갱신해주면 될 것이다. 따라서 초기값은 모두 Infinity로 초기화해주자.

// 주어진 board의 크기 -- 가독성을 위해 선언 (생략가능)
const N = board.length;
const new_board = new Array(N+2).fill().map(_ => new Array(N+2).fill(1));
const costs = new Array(N+2).fill().map(_ => new Array(N+2).fill(Infinity));

// new_board 값을 모두 1로 초기화 했으므로
// 테두리만 1로 남겨두고 기존 board 영역을 
// board 값과 동일하게 변경해주어야 한다.
for(let i = 0; i < N; i++) {
  for(let j = 0; j < N; j++) {
    new_board[i+1][j+1] = board[i][j];
  }
}

BFS 탐색을 돌릴 모든 초기값을 정의해주었다. 따라서 이젠 최소 건설 비용을 구하기 위해 BFS 탐색을 구현해주자. 먼저 초기 queue 값을 위에서 언급한 바와 같이 [Y좌표, X좌표, 방향, 가격]의 형태로 넣어주자.

현재 계산된 건설 비용보다 costs에 저장된 건설 비용이 더 크다면 이를 갱신해주어야 하기 때문에 해당 조건이 참인 경우에 값을 갱신하고 탐색을 하도록 해주자. 참고로 초기 costs의 모든 값은 Infinity이기 때문에 첫 시작은 항상 현재 가격보다 값이 클 것이다.

따라서 갱신이 이루어진 경우에 BFS 탐색을 진행하게 된다. 다음에 나아갈 방향을 계산해주기 위해 위에서 구현한 로직을 그대로 적용해줄 것이다. 즉 다음에 진행할 방향은 (현재방향 + directions의 각 원소) % 4 의 결과값이 될 것 이다. 이 값과 현재 (X, Y) 좌표를 위에서 구현한 getDirection 함수에 인자로 전달해주면 다음의 좌표를 얻을 수 있다.

얻은 좌표값이 벽인지 아닌지를 체크하여 벽이 아니라면 해당 값을 queue에 넣어주도록 하자. 이때 가격을 계산해주어야 하는데, 문제 조건에 따르면 직선 경로의 가격은 100원이고 코너링의 경우는 500원이 추가로 소요된다. 이때 코너링의 경우는 직선 경로에 해당됨과 동시에 별도의 코너링 비용이 요구되는 것과 같다. 따라서 코너링에 해당하는 방향인 경우에는 총 600원을 기존 가격에 더해주도록 하자. 직선이냐 아니냐를 구분하는 기준은 directions의 원소값이 0인 경우가 항상 직선이 될 것이다. 또한 초기값은 이전 방향이 없기 때문에 초기값에서 출발하는 모든 방향 역시 직선경로로 간주할 수 있다. 이에 유의하여 가격을 계산해주도록 하자.

위 구성요소를 모두 구현하면 다음과 같다.

// 초기 자동차의 좌표는 (1, 1)이다. new_board의 크기가 board보다 크기때문에
// 위와 같이 좌표값으로 바로 접근이 가능하다.
// 초기값은 이동한 방향이 없는 상태이다. 따라서 ''의 비유효값을 넣어준다.
// 초기 좌표는 건설비용이 없는 상태이므로 0원으로 출발한다.
const queue = [ [1, 1, '', 0] ];

while(queue.length) {
  const [Y, X, direction, price] = queue.shift();
  
  // 현재 좌표의 가격보다 이전에 기록된 건설 비용이
  // 더 큰 경우에 이를 갱신하고 탐색을 진행한다.
  if(costs[Y][X] >= price) {
    costs[Y][X] = price;
    
    for(const dir of directions) {
      // 역방향을 제외한 다음 방향을 구하고
      const direct = (direction + dir) % 4;
      // 해당 방향을 진행한 다음 좌표를 계산
      const [next_Y, next_X] = getDirection(Y, X, direct);
      
      // 계산된 다음 좌표에 벽이 없다면
      if(!new_board[next_Y][next_X]) {
        // 현재가격 + 직선이냐 코너이냐 구분하여 추가
        const cost = price + (direction === '' || dir === 0 ? 100 : 600);
        queue.push([next_Y, next_X, direct, cost]);
      }
    }
  }
}

// 종착지는 (N, N) 이므로 모든 좌표의 건설비용을
// 담고 있는 costs에서 해당 좌표값 반환
return costs[N][N];

전체코드

좀 더 일반적인 방법으로 방문여부를 체크하는 변수를 따로 두고, 또 일일이 이동방향을 직접 계산하여 진행하는 방법으로 진행해도 통과할 수 있다. 이 부분은 다른 사람의 풀이를 참고하면 좋을 듯 하다. 주석을 제외한 전체 코드는 다음과 같다.

function solution (board) {
  const N = board.length;
  const costs = new Array(N+2).fill().map(_ => new Array(N+2).fill(Infinity));
  const new_board = new Array(N+2).fill().map(_ => new Array(N+2).fill(1));
  for(let i = 0; i < N; i++) {
    for(let j = 0; j < N; j++) {
      new_board[i+1][j+1] = board[i][j];
    }
  }
  
  const queue = [ [1, 1, '', 0] ];
  const directions = [0, 1, 3];
  
  while(queue.length) {
    const [Y, X, direction, price] = queue.shift();
    
    if(costs[Y][X] >= price) {
      costs[Y][X] = price;
      
      for(const dir of directions) {
        const direct = (direction + dir) % 4;
        const [next_Y, next_X] = getDirection(Y, X, direct);
        
        if(!new_board[next_Y][next_X]) {
          const cost = price + (direction === '' || dir === 0 ? 100 : 600);
          queue.push([next_Y, next_X, direct, cost]);
        }
      }
    }
  }
  
  return costs[N][N];
}

const getDirection = (Y, X, dir) => {
  if(dir === 0) return [Y, X+1];
  else if(dir === 1) return [Y+1, X];
  else if(dir === 2) return [Y, X-1];
  else return [Y-1, X];
}