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

문제

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

프로그래머스

 

---

 

문제 개요

• 문제 설명
  N x N 크기의 격자 형태의 도면에서 출발점 (0,0)부터 도착점 (N-1, N-1)까지 자동차 경주로를 건설해야 합니다.
  경주로는 직선 도로와 코너로 구성되며, 각 비용은 다음과 같습니다:
  • 직선 도로: 100원
  • 코너: 500원
    격자는 0(빈 칸) 또는 1(벽)으로 이루어져 있으며, 벽이 있는 칸을 지나갈 수 없습니다.
    상하좌우로 이동하며 최소 비용으로 경주로를 완성해야 합니다.
• 목표
  최소 비용으로 경주로를 건설하는 비용을 반환하는 문제입니다.

 

접근 방법

1. BFS (너비 우선 탐색)를 활용한 최단 경로 탐색

• 출발점 (0,0)에서 시작하여 상, 하, 좌, 우로 이동하면서 도착점 (N-1, N-1)까지의 최소 비용을 구해야 합니다.
• 최단 경로 탐색에 가장 적합한 알고리즘인 BFS를 사용합니다.

2. 이동 비용 계산 방식

• 직선 도로의 비용은 100원이며, 코너를 만드는 경우 500원이 추가됩니다.
• 이전 이동 방향과 현재 이동 방향이 같은 경우, 직선 도로 비용(100원)만 더해집니다.
• 이전 이동 방향과 현재 이동 방향이 다른 경우, 코너 비용(500원)이 추가로 발생합니다.

3. 방문 비용 관리 (3차원 DP 테이블)

• BFS를 수행하면서 이동 시 비용을 관리하기 위해 3차원 비용 테이블 cost를 사용합니다.
• cost[r][c][d]: (r, c) 위치에 d 방향으로 도착했을 때의 최소 비용을 저장합니다.
• d: 0 (위), 1 (왼쪽), 2 (아래), 3 (오른쪽)
• 각 위치에 대해 도달하는 방향별 최소 비용을 비교해가며 탐색합니다.

4. 유효한 이동 조건

• 격자 범위를 벗어나면 안 됩니다.
• 이동하려는 칸이 벽(1)이면 안 됩니다.
• 새로운 비용이 현재 저장된 비용보다 작을 때만 갱신합니다.

5. 알고리즘 흐름

1. BFS 큐에 출발점 (0,0)을 초기 비용 0과 함께 삽입합니다. 초기 이동 방향은 -1로 설정합니다.
2. 큐에서 위치를 하나씩 꺼내 상하좌우 이동을 시도합니다.
3. 다음 위치에 도달 시 비용을 계산합니다:
   • 같은 방향: 현재 비용 + 100
   • 다른 방향 (코너): 현재 비용 + 600
4. 새로운 비용이 기존 비용보다 작다면 갱신하고, 큐에 새로운 위치를 추가합니다.
5. 도착점 (N-1, N-1)에 도달했을 때, 모든 방향별 비용 중 최소값을 반환합니다.

 

코드

import java.util.*;
class Solution {
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static int[][][] cost;
    public int solution(int[][] board) {
        int answer = 0;
        cost = new int[board.length][board[0].length][4];
        
        for(int[][] a : cost) {
            for(int[] b : a) {
                Arrays.fill(b, Integer.MAX_VALUE);
            }
        }
        
        return bfs(board);
    }
    
    public int bfs(int[][] board) {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(0,0,0,-1));
        cost[0][0][0] = 0;
        
        while(!q.isEmpty()) {
            Pos cur = q.poll();
            
            for(int i=0; i<4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                
                if(nr<0 || nc<0 || nr>=board.length || nc>=board[0].length || board[nr][nc]==1) continue;
                int newCost = cur.cost + (cur.dir==i || cur.dir==-1 ? 100 : 600);
                if(cost[nr][nc][i] > newCost) {
                    cost[nr][nc][i] = newCost;
                    q.add(new Pos(nr, nc, newCost, i));
                }
            }
        }
        int n = Integer.MAX_VALUE;
        for(int i=0; i<4; i++){
            n = Math.min(n, cost[board.length-1][board[0].length-1][i]);
        }
        return n;
    }
    
    class Pos{
        int r, c, cost, dir;
        public Pos(int r, int c, int cost, int dir) {
            this.r = r;
            this.c = c;
            this.cost = cost;
            this.dir = dir;
        }
    }
}