이번에 풀어본 문제는
프로그래머스 경주로 건설 입니다.

📕 문제 링크

❗️코드

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

class Road {
    int x,y;
    int dir;
    int price;

    public Road(int x, int y, int dir, int price) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.price = price;
    }
}
class Solution {
    static int N;
    static boolean[][] map;
    static int[][][] isVisited;
    static int[] dx = {-1, 0, 1, 0}; //상 좌 하 우
    static int[] dy = {0, -1, 0, 1};
    public int solution(int[][] board) {
        N = board.length;
        map = new boolean[N][N];
        isVisited = new int[4][N][N];
        Queue<Integer> answerQ = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] > 0) {
                    //true 면 벽
                    map[i][j] = true;
                }
            }
        }
        map[0][0] = true;

        Queue<Road> q = new LinkedList<>();
        for (int idx = 2; idx < 4; idx++) {
            int x = dx[idx];
            int y = dy[idx];
            if (!map[x][y]) {
                q.add(new Road(x, y, idx, 100));
                isVisited[idx][x][y] = 100;
            }
        }
        
        while (!q.isEmpty()) {
            Road cur = q.poll();

            if ((cur.x == N - 1) && (cur.y == N - 1)) {
                answerQ.add(cur.price);
                continue;
            }

            for (int idx = 0; idx < 4; idx++) {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];
                int tmpDir = cur.dir;
                int tmpPrice = cur.price + 100;

                // 유효성 검증
                if (!isValid(mx, my) || map[mx][my]) continue;

                // 방향 체크
                if (tmpDir != idx) {
                    tmpDir = idx;
                    tmpPrice += 500;
                }

                // 방문처리
                if ((isVisited[tmpDir][mx][my] == 0) || isVisited[tmpDir][mx][my] > tmpPrice) {
                    isVisited[tmpDir][mx][my] = tmpPrice;
                    q.add(new Road(mx, my, tmpDir, tmpPrice));
                }
            }
        }
        return answerQ.poll();
    }
    static boolean isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}

📝 풀이

벽을 피해 최소 가격으로 길을 만드는 문제입니다. 길을 만드는 비용은 100원, 방향이 꺾이면 500원이 추가됩니다.
동일한 방향으로 방문한 적이 있거나, 더 비싼 가격으로는 더 이상 탐색을 진행할 필요가 없으므로, 방향값을 포함한 3차원 배열을 방문배열로 활용하여 그래프 탐색을 진행하면 해결할 수 있습니다.

📜 후기

시작 위치가 벽일 경우를 고려하지 못해 조금 어이없게 시간이 지체되었습니다.. ㅠㅠ