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

경주로 건설 

문제) https://programmers.co.kr/learn/courses/30/lessons/67259

풀이)

헤매다가 질문글을 보고 오류를 찾은 문제이다.

참고 질문글) https://programmers.co.kr/questions/12180

PQ와 DP를 이용하고, 새로운 비용이 작거나 같을 경우만 무조건 업데이트 시키면서 이동가능하게 했었는데

이동 방향에 따라 비용의 대소가 역전되는 경우가 있었다.

그래서 DP를 이용할 때 방향까지 저장해서 풀었다.

int dp[i][j][k] = (i,j)위치에 k방향으로 도달했을 때까지 든 최소 비용

과정

1. 비용을 Memoization할 배열을 모두 나올 수 없는 최대 비용으로 초기화.( INF = 987654321 )

2. 처음 출발할 칸 즉, (0,0)위치의 배열 값은 0으로 초기화.

3. PQ를 이용해서 비용을 갱신하며 이동.

   * 코너 판단은 따로 bool 함수를 선언해서 해줬다.

     방향이 상 0 하 1 인데 이동할 방향이 좌 2 , 우 3 이면 코너를 만들었다고 판단.

     

4. (n-1, n-1)위치의 배열 값 중 최소값을 answer에 저장하여 return.

코드)

#include <string>
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321
int dp[25][25][4];
int n;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

bool curve(int d1,int d2){
    if(d1 == 0 || d1 == 1){//상하
        if(d2 == 2 || d2 == 3) return true;
    }
    else{
        if(d2 == 0 || d2 == 1) return true;
    }
    return false;
}
struct Info {
    int y, x, dir, cost;
    Info() {}
    Info(int y, int x, int dir,int cost) {
        this->y = y;
        this->x = x;
        this->dir = dir;
        this->cost = cost;
    }

};
struct cmp {
    bool operator()(const Info &a,const Info &b) {
        if (a.cost == b.cost) {
            return a.y > b.y;
        }
        return a.cost > b.cost;
    }
};
int solution(vector<vector<int>> board) {
    int answer = INF;
    n = board.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for(int k=0; k<4; k++) dp[i][j][k] = INF;
        }
    }
    for (int k = 0; k < 4; k++) dp[0][0][k] = 0;

    priority_queue <Info,vector<Info>,cmp> qu;

    for (int i = 0; i < 4; i++) {
        qu.push({0,0,i,0});
    }
    while (!qu.empty()) {
        int y = qu.top().y;
        int x = qu.top().x;
        int dir = qu.top().dir;
        int cost = qu.top().cost + 100;
        qu.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            int next_cost = cost;

            if (ny < 0 || ny >= n || nx < 0 || nx >= n || board[ny][nx] == 1) continue;
            if (curve(dir, i)) {
                next_cost += 500;
            }
            if (dp[ny][nx][i] >  next_cost) {
                dp[ny][nx][i] = next_cost;
                qu.push({ ny,nx,i,next_cost });
            }
        }

    }
    for (int k = 0; k < 4; k++) {
        if(answer > dp[n-1][n-1][k]) answer = dp[n-1][n-1][k];
    }

    return answer;
}