[프로그래머스] 경주로 건설 - Java 자바

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

프로그래머스

 

개념: bfs, 그래프 탐색

 

 

문제

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

 

예시

 

예를 들어, 그림은 직선 도로 6개와 코너 4개로 구성된 임의의 경주로 예시이며, 건설 비용은 6 x 100 + 4 x 500 = 2600원 입니다.

 

 

---

 

 

풀이

전체코드

import java.util.*;

class Solution {
    static int n, answer;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int[][][] visited;  // [x][y][방향]

    static class Car implements Comparable<Car> {
        int x;
        int y;
        int cost;
        int dir;

        public Car(int x, int y, int cost, int dir) {
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.dir = dir;
        }

        @Override
        public int compareTo(Car other) {
            return this.cost - other.cost;
        }
    }
    
    public static void bfs(int[][] board) {
        PriorityQueue<Car> pq = new PriorityQueue<>();
        pq.add(new Car(0, 0, 0, -1)); // 초기 방향 -1
        
        // 모든 위치의 모든 방향에 대해 최대값으로 초기화
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < 4; k++) {
                    visited[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }

        while (!pq.isEmpty()) {
            Car current = pq.poll();

            if (current.x == n - 1 && current.y == n - 1) {
                answer = Math.min(answer, current.cost);
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                if (nx < 0 || ny < 0 || nx >= n || ny >= n || board[nx][ny] == 1) {
                    continue;
                }

                // 비용 계산
                int newCost = current.cost;
                if (current.dir == -1) {  // 시작점
                    newCost += 100;
                } else if (current.dir == i) {  // 직진
                    newCost += 100;
                } else {  // 코너
                    newCost += 600;
                }

                // 같은 위치, 같은 방향으로 도착했을 때 비용이 더 작은 경우에만 갱신
                if (visited[nx][ny][i] > newCost) {
                    visited[nx][ny][i] = newCost;
                    pq.add(new Car(nx, ny, newCost, i));
                }
            }
        }
    }
    
    public int solution(int[][] board) {
        answer = Integer.MAX_VALUE;
        n = board.length;
        visited = new int[n][n][4];  // 3차원 배열
        bfs(board);
        return answer;
    }
}

 

 

`visited` 배열에서도 방향을 고려해야 하는 이유:

• 같은 위치라도 도착하는 방향에 따라 이후의 최소 비용이 달라질 수 있기 때문
• Car 객체의 `dir` 외 별개로, 각 위치에 각 방향으로 도착했을 때의 최소 비용을 따로 관리한다.