[프로그래머스] 경주로 건설 / 2020 카카오 인턴십 - JAVA

🖇️ 문제 링크

코딩테스트 연습 - 경주로 건설

건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다. 제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다. 설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.

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

 

---

📝 문제 분석

[0, 0]에서 [N - 1, N - 1]까지 도달하는 그래프 탐색 문제입니다.

탐색하는 방향에 따라서 비용이 달라지기 때문에 방향에 따른 최솟값을 저장하고 있어야 합니다. 여기서는 세로 방향과 가로 방향만 알면 되기 때문에 2가지 방향으로 설정하였습니다.

진행 중인 방향으로 다음 탐색 예정인 칸이 이미 최소 탐색 비용이라면 더 이상 탐색하지 않습니다.

 

 

---

⌨️ 코드

import java.util.*;

class Solution {
    public int solution(int[][] board) {
        int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1};
        int N = board.length;

        int[][][] cost = new int[N][N][2];
        
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                Arrays.fill(cost[i][j], (int)1e9);

        Queue<int[]> queue = new LinkedList<>();
        cost[0][0][0] = 0;
        cost[0][0][1] = 0;
        queue.add(new int[]{0, 0, 0});
        queue.add(new int[]{0, 0, 1});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();

            for (int d = 0; d < 4; d++) {
                int ny = cur[0] + dy[d];
                int nx = cur[1] + dx[d];
                int nc = cost[cur[0]][cur[1]][cur[2]] + ((cur[2] + d) % 2 == 0 ? 100 : 600);
                
                if (ny < 0 || nx < 0 || ny >= N || nx >= N || board[ny][nx] == 1 || cost[ny][nx][d % 2] <= nc) continue;
                
                cost[ny][nx][d % 2] = nc;
                queue.add(new int[]{ny, nx, d % 2});
            }
        }

        int[] ans = cost[N - 1][N - 1];
        return Math.min(ans[0], ans[1]);
    }
}

 

Uploaded by Notion2Tistory v1.1.0