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

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

[ 풀이 방법 ]

 우선순위 큐를 이용한 BFS로 문제를 해결하였다.

 board의 빈 칸을 INF, 벽이 있는 칸을 -1로 초기화하고, (0, 0)부터 시작하여 우선순위 큐를 이용해 board의 특정 칸까지의 도로 건설 비용이 최소가 되는 순서로 BFS를 수행하며 board에 특정 칸까지의 도로 건설 비용이 최소값이 되는 경로만을 탐색하고 최소 비용을 board에 저장하였다. 탐색이 종료된 후 (N-1, N-1)에 저장된 값을 출력하여 문제를 해결하려 하였다.

 

 그러나 2개의 테스트 케이스가 틀렸고, 질문하기를 참고하여 원인을 찾을 수 있었다.

 board의 특정 칸에 나중에 도착한 도로(board의 특정 칸까지의 도로 건설 비용이 더 큰 도로)가 (N-1, N-1)까지의 도로 건설 비용은 더 작을 수 있기 때문이었는데, 예를 들어 board의 특정 칸까지의 두 경로가 존재할 때, 한 경로가 해당 칸까지 든 비용은 적지만 다음 칸으로 이동하기 위해 코너를 건설해야 하고, 한 경로는 해당 칸까지 든 비용은 더 크지만 다음 칸으로 이동하기 위해 코너를 건설할 필요가 없다면, 500원의 비용 차이가 줄어들게 된다.

 

 따라서, board의 특정 칸까지의 도로 건설 비용이 500원 이내의 차이라면 방문을 허락하도록 수정하여 문제를 해결할 수 있었다.

 

[ 회고 ]

 접근 방법을 생각할 때, 특정 칸에 먼저 도착하는 경로가 항상 정답이 되는가를 검증해야 한다는 생각은 했지만 검증할 방법을 생각하지 못했고, 우선순위 큐를 이용해 풀 수 있는 문제가 맞는지 확신하지 못했기 때문에 우선 문제를 풀어보고 정답이 나오는지 확인하려 하였다.

 

 구현을 완료하고 제출하여 테스트 케이스 중 일부가 틀렸을 때, 위에서 생각한 부분에서 틀렸다는 것을 깨닫고 입출력 예를 검증하였다면 충분히 풀 수 있는 문제였다고 생각하지만, 접근 방법과 구현 계획을 적거나 구체화 하지 않아 구현 과정에서 검증이 필요한 부분을 까먹고 말았다. 

 

 구현 방법에 대한 확신이 없더라도 일단 적으면서 구현 계획을 구체화하고 검증이 필요한 부분에 대해서도 주의하여 문제를 풀어야 할 것이다.

 

[ 정답 코드 ]

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Road {
    int x; int y;
    int cost; int dir;
    
    Road(int x, int y, int cost, int dir) : x(x), y(y), cost(cost), dir(dir) {}
};

struct cmp {
    bool operator()(Road r1, Road r2) {
        if(r1.cost == r2.cost && r1.y == r2.y && r1.x == r2.x) return r1.dir < r2.dir;
        if(r1.cost == r2.cost && r1.y == r2.y) return r1.x < r2.x;
        if(r1.cost == r2.cost) return r1.y < r2.y;
        return r1.cost > r2.cost;
    }
};

int N;

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, -1, 0, 1};

int answer = 0;

void bfs(vector<vector<int>>& board) {
    
    priority_queue<Road, deque<Road>, cmp> pq;
    pq.emplace(0, 0, 0, 2);
    pq.emplace(0, 0, 0, 3);
    board[0][0] = 0;
    
    while (!pq.empty()) {
        int x = pq.top().x;
        int y = pq.top().y;
        int cost = pq.top().cost;
        int dir = pq.top().dir;
        pq.pop();
        
        if(board[x][y] > cost) board[x][y] = cost;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dirX[i];
            int ny = y + dirY[i];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            
            int nCost = cost + ((i == (dir+1)%4 || i == (dir+3)%4) ? 600 : 100);
            
            if(board[nx][ny] >= 0 && board[nx][ny] + 500 >= nCost) {
                
                pq.emplace(nx, ny, nCost, i);
            }
        }
    }
    
    answer = board[N-1][N-1];
}

int solution(vector<vector<int>> board) {
    
    N = int(board.size());
    
    vector<vector<int>> aux(N, vector<int>(N, 1<<30));
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(board[i][j] == 1) {
                aux[i][j] = -1;
            }
        }
    }
    
    bfs(aux);
    
    return answer;
}