[프로그래머스 Lv3] : 경주로 건설

문제 링크

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

프로그래머스

죠르디가 경주로를 건설하는 데 필요한 최소 비용을 계산할 수 있도록 도와주자.

 

풀이

인접한 상하좌우로 움질일 수 있으며 직선 도로를 건설하는 데는 100원, 코너를 건설하는 데는 500원이 소요된다.

즉, 같은 방향으로 이동할 때는 도로만 건설하면 되니까 100원

다른 방향으로 이동할 때는 도로 + 코너를 건설해야하므로 600원의 비용이 발생한다.

 

"방향"이 중요한 요소임을 알 수 있다.

 

최소 비용을 출력해야 하므로 "최단거리" 알고리즘을 사용해야 한다.

그 중에서 나는 다익스트라 알고리즘을 사용했다.

 

기존의 다익스트라 알고리즘은 각 칸마다 최단거리를 저장했다.

하지만 이 문제에서는 임의의 칸에 도착했을 때, 차가 어떤 방향을 바라보고 있는 지도 중요하다.

그래서 좌표 + 차가 바라보고 있는 방향마다 최단거리를 따로 계산했다.

 

우선순위 큐에 {비용, 방향}, {방문할 칸의 좌표} 를 저장했다.

거리를 저장하는 Dist 배열을 Dist[4][25][25] 칸으로 만들어 첫번째 인덱스는 방향으로 설정했다.

나는 0 = 상, 1 = 하, 2 = 좌, 3 = 우. 이렇게 생각했다.

 

최종적으로 Dist[0 ~ 3][n-1][n-2] 네 개의 값 중 최소값이 정답이 된다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 25 + 5;
const int INF = INT_MAX;
 
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int Dist[4][MAX_N][MAX_N];
//bool visited[MAX_N][MAX_N];
 
bool is_ok(pair<int,int> pos, vector<vector<int>> board){
    int n = board.size();
    if(pos.first < 0 || pos.first >= n || pos.second < 0 || pos.second >= n
      || board[pos.first][pos.second])
        return false;
    return true;
}
 
void BFS(vector<vector<int>> board){
    priority_queue<pair<pair<int,int>, pair<int,int>>> pq;
    
    int board_size = board.size();
    
    pq.push({{0,1},{0,0}});
    pq.push({{0,3},{0,0}});
    
    while(!pq.empty()){
        pair<int,int> now = pq.top().second;
        int cost = -pq.top().first.first;
        int direction = pq.top().first.second;
        pq.pop();
        
        if(Dist[direction][now.first][now.second] != INF)
            continue;
        
        Dist[direction][now.first][now.second] = cost;
        
        if(now.first == board_size - 1 && now.second == board.size() -1)
            continue;
        
        for(int i = 0; i<4; i++){
            pair<int,int> next = {now.first + dy[i], now.second + dx[i]};
            int acost;
            if(direction == i)
                acost = cost + 100;
            else if(direction != i)
                acost = cost + 600;
            if(is_ok(next, board) && Dist[i][next.first][next.second] == INF)
                pq.push({{-acost, i}, next});
        }
    }
}
 
int solution(vector<vector<int>> board) {
    int answer = INF;
    int n = board.size();
    for(int i = 0; i<=board.size(); i++)
        for(int j = 0; j<=board.size(); j++)
            for(int d = 0; d<4; d++)
                Dist[d][i][j] = INF;
    
    BFS(board);
    
    for(int i = 0; i<4; i++)
        answer = min(answer, Dist[i][n-1][n-1]);
    
    return answer;
}