[프로그래머스/Java] Lv.3 - 경주로 건설

승래·2026년 3월 26일

프로그래머스 Lv.3 - 경주로 건설

요구사항

(0,0)에서 (n-1,n-1)까지 경주로를 건설하는 최소 비용을 구하는 문제
직선 도로: 100원, 코너(커브): 500원 추가
방향이 바뀌면 100 + 500 = 600원

접근 방식

BFS + 방향별 최소 비용 으로 풀었다.

왜 visit을 3차원으로 관리해야 하는가?

같은 칸이라도 어떤 방향으로 도달했냐에 따라 이후 비용이 달라짐

예: (2,3)에 방향=오른쪽으로 600 도달
    (2,3)에 방향=아래로 700 도달

방향=오른쪽(600)이 더 싸지만
다음에 아래로 가면 커브 추가 → 1200

방향=아래(700)에서 아래로 직진 → 800
→ 결국 방향=아래 경로가 더 유리!

따라서 visit[x][y][dir] 3차원 배열 필요

방향 전환 비용

diff = |현재방향 - 다음방향|
diff == 0: 직진 → +100
diff == 1 or 3: 커브 → +600
diff == 2: 반대 방향 → skip

시작점 처리

(0,0)에서 첫 이동은 방향 무관하게 100원
(0,1)과 (1,0)이 벽인지 확인 후 큐에 추가

코드

import java.util.*;

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

class Solution {
    int n, answer;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};
    int[][][] visit;

    public int solution(int[][] board) {
        answer = Integer.MAX_VALUE;
        n = board.length;
        visit = new int[n][n][4];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < 4; k++)
                    visit[i][j][k] = Integer.MAX_VALUE;

        bfs(board);
        return answer;
    }

    public void bfs(int[][] board) {
        Queue<Point> q = new LinkedList<>();

        // 시작점에서 첫 이동은 방향 무관하게 100원
        if (board[0][1] == 0) { q.offer(new Point(0, 1, 100, 3)); visit[0][1][3] = 100; }
        if (board[1][0] == 0) { q.offer(new Point(1, 0, 100, 2)); visit[1][0][2] = 100; }

        while (!q.isEmpty()) {
            Point p = q.poll();

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

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

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

                int diff = Math.abs(p.dir - i);
                int cost;

                if (diff == 1 || diff == 3) {
                    cost = p.cost + 600;
                } else if (diff == 0) {
                    cost = p.cost + 100;
                } else {
                    continue; // 반대 방향 skip
                }

                if (visit[nx][ny][i] <= cost) continue;
                visit[nx][ny][i] = cost;
                q.offer(new Point(nx, ny, cost, i));
            }
        }
    }
}