프로그래머스 - 경주로 건설 (C++)

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

프로그래머스

 

다익스트라를 응용하면 될 것이라 생각했다.

DP배열을 만들고 계속 갱신해나가며 최적의 길을 찾으면 된다고 생각했다. 

그러나 다익스트라가 가능하려면 한가지 강력한 전제 조건이 필요하다.

 

지금 dp값 보다 큰 값은 절대로 다시 체크하지 않아도 된다.

 

무슨말이냐면 지금 dp[2][2] = 30 이라하였을 때, 순회하다가 다시 dp[2][2]를 만났을 때 현재 값이 31이라면 가지 않겠다는 의미이다. 

 

그러나 이 문제는 그렇지 않다. 더 큰 값이여도 더 최적인 경우가 존재한다. 때문에 이문제는 일반적인 다익스트라로는 풀어낼 수 없다. 

 

여기서 알아야하는 스킬은 3차원 배열 dp이다. dp에 단순히 값만 저장하는 것이 아니라 방향까지 고려하는 스킬이다.

한 2,2를 예로 들어보면 2,2로 도달할 수 있는 방향은 동서남북 4가지이다. 다시말하면 4방향으로 들어오는 모든 경우를 크던 작던 봐야한다는 뜻이다.

그러나 같은 방향으로 들어올 때는 얘기가 다르다. 같은 방향이라면 위의 전제가 성립된다. 다시보지 않아도 된다는 의미이다. 여기까지 생각을 했다면 이제부터는 비교적 쉽다. 

 

디테일하게 생각해보면 우선 bfs가 가장 적당하다. bfs를 순회하며 각 인접 노드를 방문하고, 각 큐에는 지금까지 돈을 얼마나 썼는지 가지고 있어야할 것이다. 여기서 dp에 계속 저장해놓고 쓰려고 시도했는데 각자 시뮬레이션을 해야하기 때문에 각자 큐에 값을 가지고 있는 것이 타당하다. (이 부분이 아직 생각 정리가 덜 된 것 같다. 추가적인 사고가 필요하다)

 

그러므로 큐에 담아야할 정보는 좌표, 코너인지 아닌지 알기 위한 이전의 좌표, 지금까지 쓴 돈 이렇게 된다.

정답 코드는 다음과 같다.

#include <string>
#include <queue>
#include <vector>
#include <iostream>
#define INF 1000000
using namespace std;

int dp[26][26][4];

int answer = INF;

void init(){
    for(int i = 0; i < 26; i++){
        for(int j = 0; j < 26; j++){
            for(int k = 0; k < 4; k++){
                dp[i][j][k] = INF;
            }
        }
    }
}

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int N;
bool check(int x, int y){
    return x < N && x > -1 && y < N && y > -1;
}

int solution(vector<vector<int>> board) {
    N = board.size();
    queue<pair<pair<pair<int, int>, pair<int, int>> , int>> q;
    
    q.push({{{0, 0},{0, 0}}, 0});
    init();    
    dp[0][0][0] = 0;
    dp[0][0][1] = 0;
    dp[0][0][2] = 0;
    dp[0][0][3] = 0;
    
    
    while(!q.empty()){
        int now_x = q.front().first.first.first;
        int now_y = q.front().first.first.second;
        int pre_x = q.front().first.second.first;
        int pre_y = q.front().first.second.second;
        int cost = q.front().second;
        q.pop();
        
        if(now_x == N - 1 && now_y == N - 1) { 
            answer = min(cost, answer);
            continue;                                     
        }
        for(int i = 0; i < 4; i++){
            int next_x = now_x + dx[i];
            int next_y = now_y + dy[i];
            
            int next_cost = cost;
            if(pre_x != next_x && pre_y != next_y) next_cost += 600;
            else next_cost += 100;
            
            if(check(next_x, next_y) && board[next_x][next_y] == 0){
                if(dp[next_x][next_y][i] >= next_cost){                
                    q.push({{{next_x, next_y},{now_x, now_y}}, next_cost});

                    dp[next_x][next_y][i] = next_cost;
                }                    
            }
        }
    }
    
    return answer;
}