[프로그래머스] 경주로 여행 - JAVA

링크 : https://programmers.co.kr/learn/courses/30/lessons/67259?language=java# 

코딩테스트 연습 - 경주로 건설

 

- 풀이

 : 벽을 지나갈 수 없는 곳을 제외하고는 dfs 또는 bfs 를 통해 도착지점을 찾는 문제

 : 다시 최소 비용으로 다시 온 곳은 board 상의 위치에 값을 대입해서 최소 비용으로만 처리하게 해야 함

 : 방향이 바뀌는 곳은 500만 더해지는 것이 아니고 방향 바뀌고 한칸 전진 이기 때문에 600이 더해져야 함.

 : 첫 출발은 모두 직진이기때문에 방향 관계없이 100 더해 짐.

 

 

 

class Solution {
    int n = 0;
    int minCost;
    int[] dx = new int[]{0, 1, 0, -1};
    int[] dy = new int[]{1, 0, -1, 0};
    boolean[][] visited;
    int[][] map;
    
    class Point {
        int x;
        int y;
        int dir; // 0 : right, 1 : down, 2: left, 3: up;
        int cost;
        public Point(int x, int y, int dir, int cost) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cost = cost;
        }
    }
    
    public int solution(int[][] board) {
        n = board.length;
        visited = new boolean[n][n];
        map = board;
        visited[0][0] = true;
        dfs(new Point(0, 0, -1, 0));
        return minCost;
    }
    
    private void dfs(Point p) {
        if (p.x == n-1 && p.y == n-1) {
            // 탈출
            minCost = minCost == 0 ? p.cost : Math.min(minCost, p.cost);
            return;
        }
        
        for(int i=0;i<4;i++) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            int dir = i;
            int nCost = p.cost;
            if(p.dir == -1) {
                nCost += 100;
            } else if(p.dir == dir) {
                nCost += 100;
            } else {
                nCost += 600;
            }
            
            if(isValid(nx, ny, n) && (!visited[nx][ny] || map[nx][ny] >= nCost )) {
                visited[nx][ny] = true;
                map[nx][ny] = nCost;
                dfs(new Point(nx, ny, dir, nCost));
            }
        }
        
    }
    
    private boolean isValid(int x, int y, int n) {
        return x >= 0 && y >= 0 && x < n && y < n && map[x][y] != 1;
    }
}