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

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

프로그래머스

 

 

제일 처음에는 다익스트라 알고리즘을 사용하는 걸 떠올렸는데..

결론을 말하자면 다익스트라 알고리즘이 맞지만 [모든 방향을 고려한] 다익스트라 알고리즘이라고 할 수 있을 것 같다

(2023.02.17 맞나..? 다시 생각해보니까 다익스트라는 greedy한 알고리즘인데 dp라고 하는 게 맞지 않나..)

맨 처음 생각한 방식

시작점 [0, 0]에서부터 이동 가능한 좌표를 우선순위 큐에 삽입시키면서 최소 비용을 계산하는 방식이다

문제에서의 예시 3번으로 생각해 보면

0 0 1 0
0 0 0 0
0 1 0 1
1 0 0 0

 

좌표 [0, 0]를 기준으로 이동 가능한 다음 좌표는 [0, 1], [1, 0]. 이 둘 좌표의 비용은 각각 100이다.

이 두 좌표를 우선순위 큐에 삽입하고,

다음 기준 좌표는 우선순위 큐의 제일 위에 있는 좌표로 정하여 위의 작업을 반복한다.

만약 [0, 1] -> [1, 1]인 경우와 [1, 0] -> [1, 1] 인 경우와 같이, 큐에 삽입할 좌표가 중복되는 경우가 생긴다면 비용이 최소일 경우에만 삽입하도록 처리하였다.

 

이 방식은 각 좌표까지의 최소 비용을 기준으로 탐색을 이어나가는 건데, 위의 밑줄 친 부분처럼 처리할 경우 문제가 생긴다.

문제에서는 경주로가 직진일 경우/꺾일 경우 를 고려하여 비용이 달라지기 때문에 비용뿐만 아니라 방향까지 고려를 해 주어야 한다.

예시를 들자면

 

[0, 1] -> [1, 1] -> [1, 2]      ...(1)

[1, 0] -> [1, 1] -> [1, 2]      ...(2)

 

위의 경로 (1)과 (2)는 [1, 1]까지는 비용이 동일하게 700이지만, (1) 경로에서는 [1, 1] -> [1, 2] 과정에서 코너가 하나 더 생기기 때문에 (1)의 총 비용은 1300, (2)의 총 비용은 800이 된다.

 

이처럼 방향을 고려하지 않았을 경우에는 제대로 된 목적지까지의 최소 비용을 고려할 수 없다..

따라서 3차원 배열을 작성하여 모든 방향에서의 최소 비용을 구하면서 풀이하였다.

 

++ 

이렇게 풀이하면 시간 초과가 나지 않을까?? 라고 처음엔 생각했는데..

시간복잡도가 늘어난다기보다는 공간복잡도가 늘어나는 방식이어서 시간에는 큰 영향을 끼치지 않는다고 한다..

참고 링크

 

 

 

 

++ 3차원 배열의 인덱스는 [면][행][열] 이다.. ;;

 

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
   int[] dX = {0, 1, 0, -1};
   int[] dY = {1, 0, -1, 0};

   int[][][] isVisited;
   int gridSize;

   public int solution(int[][] board) {
      //init
      gridSize = board.length;
      isVisited = new int[4][gridSize][gridSize];    //  방향마다의 cost
      for (int i = 0; i < 4; i++) {
         for (int j = 0; j < gridSize; j++) {
            Arrays.fill(isVisited[i][j], Integer.MAX_VALUE);
         }
      }
      //출발지점 초기화
      isVisited[0][0][0] = 0;
      isVisited[1][0][0] = 0;
      isVisited[2][0][0] = 0;
      isVisited[3][0][0] = 0;

      return findMinRoutes(board);
   }

   private int findMinRoutes(int[][] board) {
      PriorityQueue<Grid> queue = new PriorityQueue<>();
      queue.add(new Grid(0, 0, -1, 0));
      while (!queue.isEmpty()) {
         Grid currGrd = queue.poll();
         if (currGrd.x == gridSize - 1 && currGrd.y == gridSize - 1) {
            return currGrd.minCost;
         }

         for (int i = 0; i < dX.length; i++) {
            int nextX = currGrd.x + dX[i], nextY = currGrd.y + dY[i];
            if (isReachable(board, nextX, nextY)) {
               int nextCost = currGrd.minCost + calCost(currGrd, i);
               Grid newGrid;
               if (isVisited[i][nextX][nextY] < nextCost) {
                  continue;
               } else {
                  isVisited[i][nextX][nextY] = nextCost;
                  newGrid = new Grid(nextX, nextY, i, nextCost);
               }
               queue.add(newGrid);
            }
         }
      }
      return 0;
   }

   private boolean isReachable(int[][] map, int x, int y) {
      return x >= 0 && x < gridSize && y >= 0 && y < gridSize && map[x][y] == 0;
   }

   private int calCost(Grid grid, int nextDirection) {
      if (grid.routeDirection == -1 || ((grid.routeDirection + nextDirection) % 2 == 0)) {
         return 100;
      }
      return 500 + 100;
   }

}

class Grid implements Comparable<Grid> {
   int x;
   int y;

   int routeDirection;
   int minCost;

   public Grid(int x, int y, int routeDirection, int minCost) {
      this.x = x;
      this.y = y;
      this.routeDirection = routeDirection;
      this.minCost = minCost;
   }

   @Override
   public int compareTo(Grid o) {
      return this.minCost - o.minCost;
   }
}