Lv 3. 경주로 건설

 

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

프로그래머스

 

 

 

이 문제는 BFS를 사용해 격자형 경로에서 최단 비용을 계산하며,

방향 전환에 따른 코너 비용까지 고려하여 최적의 이동 경로를 찾는 문제다.

 

각 셀에서 이동 방향에 따라 비용이 달라지므로,

방향을 기록할 수 있는 3차원 배열 isVisited를 사용해

각 위치와 방향에 따른 최소 비용을 저장한다.

 

먼저 solution 메서드에서 answer를 최댓값으로 초기화하고

 bfs 메서드를 호출해 탐색을 시작한다. 

 

bfs 메서드는 시작 지점 (0,0)에서 초기 비용 0으로 시작하며,

네 방향 각각에 대해 비용을 초기화한다.

이후 큐에서 Node를 꺼내 네 방향으로 확장하며 이동 가능 여부를 체크한다.

이동할 때 직선으로 가면 비용 100이 추가되고,

방향이 바뀌면 코너 비용 500이 더해져 총 600이 추가된다.

 

이동할 위치가 보드의 범위 안에 있고 장애물이 없는 경우,

현재 경로의 비용이 더 저렴하다면 isVisited 배열을 갱신하고

큐에 새 노드를 추가해 탐색을 이어간다.

 

목적지에 도착할 때마다 answer를 최소값으로 갱신하며,

최종적으로 최단 비용을 반환한다.

 

 

import java.util.*;

class Solution {
    
    private int answer;
    
    private class Node{
        int x;
        int y;
        int d;
        int cost;
        
        public Node(int x, int y, int d, int cost){
            this.x = x;
            this.y = y;
            this.d = d;
            this.cost = cost;
        }
    }
    
    private void bfs(int n, int[][] board){
        Queue<Node> q = new ArrayDeque<>();
        int[][][] isVisited = new int[n + 1][n + 1][4];  // 각 방향 별로 비용을 기록하는 3차원 배열
        int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};  
        
        // 초기화
        q.add(new Node(0, 0, -1, 0));
        for (int i = 0; i < 4; i++) {
            isVisited[0][0][i] = 0;  // 출발 지점 비용 초기화
        }
        
        while(!q.isEmpty()){
            
            Node now = q.poll();
            
            if(now.x == n && now.y == n){
                answer = Math.min(answer, now.cost);
                continue;
            }
                
            for(int d = 0 ; d < 4 ; d++){
                int x = now.x + dir[d][0];
                int y = now.y + dir[d][1];
                int nextCost = now.cost + (now.d == d || now.d == -1 ? 100 : 600);
                
                // 범위 확인, 장애물 확인, 비용 조건 확인
                if(x >= 0 && x <= n && y >= 0 && y <= n && board[x][y] == 0) {
                    if(isVisited[x][y][d] == 0 || isVisited[x][y][d] > nextCost){
                        isVisited[x][y][d] = nextCost;
                        q.add(new Node(x, y, d, nextCost));
                    }
                }
            }
        }
    }
    
    public int solution(int[][] board) {
        int N = board.length;
        answer = Integer.MAX_VALUE;
        bfs(N - 1, board);
        return answer;
    }
}