[프로그래머스][Level3][Java] 경주로 건설

programmers.co.kr/learn/courses/30/lessons/67259

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

문제풀이

해당 문제는 최단 경로 찾기 문제이기때문에 BFS로 풀면 되는 문제였다.

또한 항상 최소 비용을 가지고 있어야 되기때문에 비용을 저장하는 배열(priceMap)을 따로 선언하여 방문 체크 하는 배열 대신 활용 하였다. priceMap에는 항상 최소 비용을 가지고 있기 때문에 경로마다 자기 자신의 비용을 가지고 있고 방향마다 검사를 진행하여 그 방향에 위치한 배열값과 비교해서 값이 작다면 priceMap에 값을 갱신하고 Queue에 집어 넣어줘서 계속 진행하면 된다.

 

코드

import java.util.*;

class Solution {
    public int solution(int[][] board) {
        int answer = Integer.MAX_VALUE;
        int N = board.length;
        Queue<Pos> qu = new LinkedList<>();
        int[][] priceMap = new int[N][N];
        int[] dx = {0,0,-1,0,1};
        int[] dy = {0,1,0,-1,0};
        
        //각 지점 마다 최소값 가질 수 있도록 MAX_VALUE로 초기화
        for(int i=0; i<N; i++) {
        	for(int j =0; j<N; j++) {
        		priceMap[i][j] = Integer.MAX_VALUE;
        	}
        }
        
        //출발 넣어주기 직진으로 
        qu.offer(new Pos(0,0,1,0));
        qu.offer(new Pos(0,0,4,0));
        
        while(!qu.isEmpty()){
            int size = qu.size();
            for(int i=0; i<size; i++){
                Pos pos = qu.poll();
                
                if(pos.x == N-1 && pos.y == N-1) continue;
                
                for(int k=1; k<5; k++){
                    int x = pos.x + dx[k];
                    int y = pos.y + dy[k];
                    int dis = pos.dis;
                    int price = pos.price;
                    
                    if(x<0 || x>=N || y<0 || y>=N || board[x][y] == 1) continue;
                    
                    //진행한 방향과 같은지 검사
                    if((dis%2==0 && k%2 ==0)||(dis%2==1 && k%2 ==1)) {
                        //priceMap에 저장된 값보다 크다면 갈 필요 없는 길
                    	if(priceMap[x][y] >= price+100) {
                    		qu.offer(new Pos(x,y,k,price + 100));
                        	priceMap[x][y] = price+100;
                    	}
                    }
                    else {
                        //코너를 도는 순간 직진과 코너 값을 더 해준다.
                    	if(priceMap[x][y] >= price+600) {
                    		qu.offer(new Pos(x,y,k,price +600));
                    		priceMap[x][y] = price+600;
                    	}
                    }
                }
            }
        }
        
        return priceMap[N-1][N-1];
    }
    
    static class Pos{
        int x;
        int y;
        int dis;
        int price;
        
        public Pos(int x, int y, int dis, int price){
            this.x = x;
            this.y = y;
            this.dis = dis;
            this.price = price;
        }
    }
}