[2020 카카오 인턴십]경주로 건설

📍 문제 설명

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

프로그래머스

 

💡 접근

마지막 테스트케이스가 꽤나 골치 아팠던 문제였다.

24번까지는 따로 방문 처리를 하지 않더라도 금액에 따라 방문 여부가 결정되니 있던 없던 차이가 별로 없었다.

25번 케이스는 오는 방향에 따른 최소 비용을 구할 수 있는 지를 판별하는 케이스였다.

 

ex) 3x3의 크기의 배열

(2,3, 동쪽)의 400원 (2, 3, 북쪽) 500원이라고 했을 때 400원이 선택 된다.

(2,3, 동쪽)에서 (3,3 북쪽) 으로의 최소 비용은 1000원이 된다.(400 + 100 + 500)

하지만 (2, 3, 북쪽)에서 갔다면 최소 비용은 600이 된다.

따라서 방향에 따른 최소 비용을 계산 해줘야 되기 때문에 3차원 배열을 이용한 풀이가 가능하다.

 

👩‍💻 코드

import java.beans.Visibility;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
    static boolean[][][] visited;

    public int solution(int[][] board) {
        int answer = Integer.MAX_VALUE;
        int n = board.length;

        Queue<RaceRoad> q = new LinkedList<>();
        q.add(new RaceRoad(0, 0, -1, 0));
        visited = new boolean[n][n][4];

        while(!q.isEmpty()) {
            RaceRoad cur = q.poll();
            if(cur.x == n-1 && cur.y == n-1) {
                answer = Math.min(cur.price, answer);
            }
            //빠르게 도착했다고 최소비용이 적은 것은 아니다.
            for(int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                int nDir = i;
                int nPrice = cur.price;
                if(nx<0 || ny<0 || nx>=n || ny>=n || board[nx][ny] == 1) continue;

                //처음은 100원
                if(cur.direction == -1) nPrice += 100;
                //방향이 같으면 100원
                else if(cur.direction == nDir) nPrice += 100;
                //방향이 다르면 코너 추가로 만들어야함
                else nPrice += 600;

                //방문한 곳은 가지 않지만 가격이 더 저렴하면 간다.
                //같은 경우에도 가보는 것이 맞다.
                if(!visited[nx][ny][nDir] || board[nx][ny] >= nPrice) {
                    visited[nx][ny][nDir]  = true;
                    board[nx][ny] = nPrice;
                    q.add(new RaceRoad(nx, ny, nDir, nPrice));
                }
            }
        }
        return answer;
    }


    private class RaceRoad {
        private int x;
        private int y;
        private int price;
        private int direction;

        public RaceRoad(int x, int y, int price) {
            this.x = x;
            this.y = y;
            this.price = price;
        }

        public RaceRoad(int x, int y, int direction, int price) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.price = price;
        }

        @Override
        public String toString() {
            return "RaceRoad{" +
                    "x=" + x +
                    ", y=" + y +
                    ", price=" + price +
                    ", direction=" + direction +
                    '}';
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();

        int[][] board = {{0,0,0},{0,0,0},{0,0,0}};
        main.solution(board);
    }
}