[프로그래머스] 경주로 건설- JAVA(자바)

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

프로그래머스

코드:

import java.util.*;

public class Main {


    public static void main(String[] args) {

        Solution solution = new Solution();
        int[][] board = {
                {0,0,1},
                {0,0,0},
                {0,0,0}
        };
        int answer = solution.solution(board);
        System.out.println("answer = " + answer);
    }
}

class Solution {
    // 상,좌,하,우
    int[] dx = {-1,0,1,0};
    int[] dy = {0,-1,0,1};
    int n;

    public int solution(int[][] board) {
        n = board.length;
        // 벽의 존재 때문에 시작점에서 아래로 가는 경우, 시작점에서 오른쪽으로 가는 경우를 따로 구해 비교해야 한다.
        return Math.min(bfs(board, new Car(0,0,0,2)), bfs(board, new Car(0,0,0,3)));
    }

    public int bfs(int[][] board, Car car){
        int[][] costBoard = new int[n][n]; // 비용 저장 board
        Queue<Car> q = new LinkedList<>();
        q.add(car);

        while(!q.isEmpty()){
            Car cur = q.poll();
            for(int i = 0; i < 4; i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 경계를 벗어나는 경우
                if(board[nx][ny] == 1) continue; // 벽인 경우
                int newCost = (cur.dir == i) ? cur.cost + 100 : cur.cost + 600; // cur.dir != i 인 경우 코너이다.
                if(costBoard[nx][ny] == 0 || (costBoard[nx][ny] != 0 && costBoard[nx][ny] > newCost)){
                    q.add(new Car(nx,ny, newCost, i));
                    costBoard[nx][ny] = newCost;
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                System.out.print(costBoard[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
        return costBoard[n-1][n-1];
    }
}

class Car{
    int x,y,cost,dir;

    public Car(int x, int y, int cost, int dir){
        this.x = x;
        this.y = y;
        this.cost = cost; // 현재 위치까지 비용
        this.dir = dir; // (x,y) 위치에서 다음 앞으로 갈 방향
    }
}