프로그래머스 - 경주로 건설(Java)

bfs 문제입니다.

 

(0,0)에서 (n,n)까지 가는 최소 비용을 구하면 됩니다.

직진(방향이 같으면) 100이 추가되고, 꺽으면(방향이 다르면) 600이 추가됩니다.

뒤돌아 가면 비용이 양의 정수로 추가되기 때문에 고려하지 않도록 합니다.

visted로 비용을 저장하되, 방향에 따라서 해당 위치의 최솟값이 달라지게 되는 것을 고려해야 합니다.

 

[구현코드]

import java.util.*;

class Solution {
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    private static class Race {
        int x, y, w, d;

        public Race(int x, int y, int w, int d) {
            this.x = x;
            this.y = y;
            this.w = w;
            this.d = d; // 0~3
        }
    }

    public static int solution(int[][] board) {
        return dfs(board);
    }

    private static int dfs(int[][] board) {
        Queue<Race> qu = new LinkedList<>();
        qu.add(new Race(0, 0, 0, -1));
        int n = board.length;
        int[][][] visited = new int[n][n][4];
        int min = Integer.MAX_VALUE;

        while (!qu.isEmpty()) {
            Race race = qu.poll();

            if (race.x == n - 1 && race.y == n - 1) {
                min = Math.min(min, race.w);
                continue;
            }

            if (race.w > min) continue;

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

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

                int nw = race.w;
                if (race.d == -1) {
                    nw += 100;
                } else if (race.d == i) {
                    nw += 100;
                } else {
                    nw += 600;
                }

                if(visited[nx][ny][i] == 0 || visited[nx][ny][i]>=nw) {
                    visited[nx][ny][i] = nw;
                    qu.add(new Race(nx, ny, nw, i));
                }
            }
        }
        return min;
    }
}