[Algorithm] Programmers :: 경주로 건설

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

프로그래머스

struct Node
{
    int y;
    int x;
    bool isRow;
    int cost;
};
 
int visited[26][26][2];
int dir[4][2] = {  {-1,0}, {1,0}, {0,-1}, {0,1}, }; // 상하좌우
 
int solution(vector<vector<int>> board) 
{
    int answer = 0;
 
    int row = board.size();
    int col = board[0].size();
 
    memset(visited, 0x3f, sizeof(visited));
 
    queue<Node> q;
    q.push({ 0,0,true,0 });
    q.push({ 0,0,false,0 });
 
    visited[0][0][0] = 0;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        bool curIsRow = q.front().isRow;
        int curCost = q.front().cost;
 
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY == row) continue;
            if (nextX < 0 || nextX == col) continue;
            if (board[nextY][nextX] == 1) continue;
            
            if ((curIsRow == true && i <= 1) || (curIsRow == false && i >= 2)) // +600조건
            {
                if (curCost + 600 < visited[nextY][nextX][!curIsRow])
                {
                    visited[nextY][nextX][!curIsRow] = curCost + 600;
                    q.push({ nextY,nextX,!curIsRow,curCost + 600 });
                }
            }
            else
            {
                if (curCost + 100 < visited[nextY][nextX][curIsRow])
                {
                    visited[nextY][nextX][curIsRow] = curCost + 100;
                    q.push({ nextY,nextX,curIsRow,curCost + 100 });
                }
            }
        }
    }
 
    return min(visited[row - 1][col - 1][0], visited[row - 1][col - 1][1]);
}

꽤나 자주 나오는 유형의 문제입니다. 만약 25번케이스만 틀릴 경우, 해당케이스에 대해 검색해보면 설명이 잘 되어있습니다.

 

결국 특정칸에 대해 어떤방향으로 들어왔는지에 대해 검사를 추가로해야하는 문제입니다. 방향검사없이 했더니 25번만 제외하고 다 통과했었지만, 25번테스트케이스를 보니 결국 검사를 해야할 것 같아서 상하 , 좌우 두가지에 대해서만 방향검사를 추가했습니다. (visited[y][x][0~1])

 

'코너'일 때 500원이 필요한 것인데, 결국 진행방향에서 직각으로 꺾었을 경우를 뜻합니다. 즉, 우측으로 진행하다 상,하로 꺾을 경우 500원이 필요하단건데 이럴경우 상,하 똑같은 경우의 수라 하나로 묶어버려도 되며 그렇기 때문에 굳이 네가지방향에 대해 검사할 필요없이 상하,좌우 두가지로 나눠도 됩니다.