프로그래머스 - 경주로 건설

프로그래머스 - 경주로 건설

bfs를 이용해서 풀 수 있는 문제이다.
주의할 점은 방향별로 cost를 따로 관리하지 않으면 TC25를 통과하지 못한다.
다음과 같이 board가 주어지면
[0, 0, 0, 0, 0, 0, 0, 0][1, 0, 1, 1, 1, 1, 1, 0]
[1, 0, 0, 1, 0, 0, 0, 0][1, 1, 0, 0, 0, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 0, 0][1, 1, 1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 1, 1, 0][1, 1, 1, 1, 1, 1, 1, 0]
row = 3, col = 4 지점에서 위에서 오는 것과 왼쪽에서 오는 것 두 가지가 존재하는데, 위에서 바로 오는 경우엔 2800이고, 우측에서 오는 경우엔 2700이다. 방향을 고려하지 않으면 (3, 4)까지는 2700이 최저인데, (4, 4)의 경우엔 위에서 오는경우에서 쭉 가면 2900, 우측에서 오는 경우로 가면 3300이 된다(방향이 꺽이기 때문에). 따라서 (4, 4)는 최저는 2900이 되어야 하는데, 방향을 고려하지 않고 최저를 기록해두면 3300이 기록되어서 최종 답은 4500이 아닌 4900이 나온다.
이를 해결하기 위해 방향별로 cost를 기록해두어야 한다.

코드는 다음과 같다.

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

using namespace std;

typedef struct __info {
    int row;
    int col;
    int dir;
    int straight;
    int corner;
}info;

int rowDir[4] = { -1, 1, 0, 0 };
int colDir[4] = { 0, 0, -1, 1 };
#define INF (1 << 28)
int solution(vector<vector<int>> board) {
    int row_size = board.size();
    int col_size = row_size;
    int answer = 0;
    int cost[4][30][30];
    int visit[4][30][30];
    for(int i=0;i<4;i++) 
        for(int j=0;j<30;j++)
            for(int k=0;k<30;k++) {
                visit[i][j][k] = 0;
                cost[i][j][k] = INF;
            }
    for(int i=0;i<4;i++) {
        visit[i][0][0] = 1;
        cost[i][0][0] = 0;
    }
    queue<info> q;
    q.push( {1, 0, 1, 1, 0} ); 
    q.push( {0, 1, 3, 1, 0} ); 
    while(1) {
        if(q.empty())
            break;
        
        info cur = q.front(); q.pop();
        if(board[cur.row][cur.col])
            continue;
        
        if(cost[cur.dir][cur.row][cur.col] > cur.straight * 100 + cur.corner * 500)
            cost[cur.dir][cur.row][cur.col] = cur.straight * 100 + cur.corner * 500;
        else 
            continue;
        
        if(cur.row == row_size - 1 && cur.col == col_size - 1)
            continue;
        for(int i=0;i<4;i++) {
            if((cur.dir + i) % 4 == 1)
                continue;
            
            int nrow = cur.row + rowDir[i];
            int ncol = cur.col + colDir[i];
            if(nrow < 0 || ncol < 0 || nrow > row_size - 1 || ncol > col_size - 1)
                continue;
            
            int nstraight = cur.straight + 1;
            int ncorner = cur.corner;
            if(i != cur.dir) 
                ncorner++;
            q.push( {nrow, ncol, i, nstraight, ncorner} );
        }
    }
    
    answer = INF;
    for(int i=0;i<4;i++) 
        answer = answer > cost[i][row_size - 1][col_size - 1] ? cost[i][row_size - 1][col_size - 1] : answer;
    
    return answer;
}