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

 이 문제는 프로그래머스 level 3 문제이다. 이 문제를 처음에 풀 때 입력이 25 * 25 = 625로 작아 백트래킹으로 풀릴 줄 알았다. 그러나 방향이 4가지이기 때문에 모든 칸이 빈칸인 경우 각 칸마다 4가지씩, 즉 어림잡아 4^625 정도로 절대 시간 안에 풀 수 없다.

 

 그래서 bfs를 떠올리게 되었고, 그 중에서 다익스트라 알고리즘과 유사한 형태가 떠올라 그 방식으로 풀었다. 다익스트라 알고리즘의 핵심은 우선순위 큐 사용인데, 처음에 방향에 따른 cost를 생각하지 않고 정해진 방향으로 풀면 정답이 나오지 않는다. 방향에 따른 루프를 시작할 때, 무조건 현재의 방향을 우선으로 고려해야 정답이 나온다. 또한 이미 저장된 cost와 현재 값을 비교할 때 그 값이 같을 때에도 큐에 값이 들어가야 한다. 왜냐하면 같은 값이라도 방향이 다르면 결과가 다르게 나오기 때문이다.

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

#define UP 0
#define LEFT 1
#define DOWN 2
#define RIGHT 3

#define INF 100000000

int dy[] = {-1, 0, 1, 0};
int dx[] = {0, -1, 0, 1};
int N;

int cost[25][25];

void init() {
    for (int y = 0; y < 25; y++) {
        for (int x = 0; x < 25; x++) {
            cost[y][x] = INF;
        }
    }
}

bool inRange(int y, int x) {
    if (0 <= y && y < N && 0 <= x && x < N) {
        return true;
    }
    return false;
}

struct node {
    int y;
    int x;
    int direction;
};

int bfs(vector<vector<int>>& board, int startY, int startX, int direction) {
    queue<node> q;
    
    cost[startY][startX] = 0;
    
    q.push({startY, startX, direction});
    
    while (!q.empty()) {
        node present = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nextDirect = (present.direction + i) % 4; // 이 부분 중요
            int ny = present.y + dy[nextDirect];
            int nx = present.x + dx[nextDirect];
            int nextCost;
            
            if (nextDirect == present.direction) {
                nextCost = cost[present.y][present.x] + 100;
            }
            else {
                nextCost = cost[present.y][present.x] + 600;
            }
            
            if (inRange(ny, nx) && board[ny][nx] == 0 && cost[ny][nx] >= nextCost) { // 이 부분 중요
                cost[ny][nx] = nextCost;
                q.push({ny, nx, nextDirect});
            }
        }
    }
    
    return cost[N-1][N-1];
}

int solution(vector<vector<int>> board) {
    int answer = INF;
    
    N = board.size();
    
    for (int i = 0; i < 4; i++) {
        init();
        answer = min(answer, bfs(board, 0, 0, i));
    }
    
    return answer;
}