[pro] 프로그래머스 level3 67259 경주로 건설 (Java) - BFS

[문제]

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

프로그래머스

 

[풀이]

BFS 문제이다.

주의할 점은, 이동 방향을 포함해서 visited를 3차원 배열로 선언한 후, 경주로 건설 비용을 저장해서 더 최소 비용인 경우에만 q에 넣어주어야 한다.

 

이동 방향을 포함해야 하는 이유는 다음과 같다.

현재 위치 {r, c, 이동 방향}에 대해서 {5,5,동쪽} = 1100, {5,5,남쪽} = 900이라고 가정하자. 만약 2차원 배열을 사용한다면 더 작은 값인 visited[5][5] = 900을 저장할 것이다. 그러나 {5, 6, 동쪽}으로 이동한다고 하면, {5,5,남쪽}의 죠르디는 코너를 돌아야 하므로 900+600 = 1500의 값을, {5,5,동쪽}의 죠르디는 직진만 하면 되므로 1100+100=1200의 비용을 갖는다. 즉, 방향성에 따라 최소 비용이 달라지기 때문에 3차원 배열을 이용해서 방향성을 기록해 비교해주어야 한다.

 

[코드]

 

import java.util.*;

class Solution {
    int answer = Integer.MAX_VALUE;
    int[][][] visited;
    int[] dr = {0, 0, 1, -1}; //동 서 남 북
    int[] dc = {1, -1, 0, 0};
    public int solution(int[][] board) {
        //경주로 건설을 위한 최소 비용. 직선 - 100원, 코너 500원
        //0 - 비어있음 1 - 벽
        
        int len = board.length;
        visited = new int[len][len][4];
        
        for(int i=0; i<len; i++){
            for(int j=0; j<len; j++){
                for(int k=0; k<4; k++){
                    visited[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }
        
        bfs(0, 0, len, board);
        
        return answer;
    }
    
    public void bfs(int r, int c, int len, int[][] board){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r, c, 0, -1));    
        
        
        while(!q.isEmpty()){
            Point p = q.poll();
            int x = p.x;
            int y = p.y;
            int m = p.money;
            int d = p.dir;

            
            if(x==len-1 && y==len-1){
               answer = Math.min(answer, m); 
            }
            
            for(int i=0; i<4; i++){
                int nr = x + dr[i];
                int nc = y + dc[i];

                if(nr<0 || nc<0 || nr>=len || nc>=len || board[nr][nc]==1 ) continue;
                
                int cost = m;
                //직선 코스
                if(d==i || d==-1){
                    cost += 100;
                }
                else{ //곡선 코스
                   cost += 600; 
                }
                
                //갱신
                if(visited[nr][nc][i] >= cost){
                    visited[nr][nc][i] = cost;
                    q.add(new Point(nr, nc, cost, i));
                }
            }
        }
        
    }
    
    static class Point{
        int x, y, money, dir;
        Point(int x, int y, int money, int dir){
            this.x = x;
            this.y = y;
            this.money = money;
            this.dir = dir;
        }
    }
}