https://yabmoons.tistory.com/634

풀이전략

• board의 최소비용을 갱신하면서 진행한다. 이전의 값에서
  직진해서 들어오는지, 꺽어서 들어오는지를 확인한다.

• 방향벡터는 어떻게 설정하냐면 상하좌우 int i = 0 ~ 3까지 확인을 하는데,
  이를 dir에 넣어서 동일한지 동일하지 않은지 확인하는 방식으로 진행한다.
  동일하다면 직진이고, 동일하지 않다면 꺽는 것을 나타낸다.

• 구하는 것이 최단 거리가 아니고, 최소비용이다.
  방문한 노드를 다시 방문햇을 때 최소비용이 나올 수도 있으므로 ,
  이 때는 불변수 사용하지 말자.

등호 사용하지 않으면 큐에 갱신이 안되므로 등호도 포함하자.

• 동일한 cost이지만 큐 추가 여부를 결정하는 것이므로 등호를 써야한다. 사용하지 않으면!
  

• 왜 이럴까에 대해서 고찰을 해보면...
  

  내 생각에는 초록부분에 도착할 때와 파란 부분에 도찰할때 cost값을 동일하지만,
  여기서 초록부분보다 파란 부분에 먼저 도착할 경우, 초록은 pass 당하게 된다.
  등호를 사용해서 초록 부분에서 다른 노드로 확장해나갈때 cost를 구해야 하므로
  등호를 사용해야 한다.

소스코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

struct road
{
    int y;
    int x;
    int dir;
    int cost;
};

//상하좌우
int dy[] = {-1,1,0,0};
int dx[] = {0,0,-1,1};

int answer = 1000000;

void bfs(vector<vector<int>>&board)
{
    int SIZE = board.size();
    
    //직선 도로 : 100원, 코너 : 500원 
    
    //해당 정점까지 도착하는데 필요한 최단cost를 가져야 하므로 
    //cost를 누적해야 하므로 cost를 가지고 있어야 한다.
    //코너를 포함한 것인지 직선도로를 사용할 것인지 유무를 알아야 한다. 
    
    vector<vector<int>>tmpCost(board.size(), vector<int>(board.size(), 1000000));
    
    queue<road>q;
    road origin = {0,0,-1,0};
    q.push(origin);
    
    while(!q.empty())
    {
        road cur = q.front();
        q.pop();
        
        if(cur.y == SIZE -1 && cur.x == SIZE -1)
        {
            answer = min(answer, tmpCost[SIZE - 1][SIZE - 1]);
            continue;
        }
        
        
        for(int i = 0; i < 4; i++)
        {
            road next;
            next.y = cur.y + dy[i];
            next.x = cur.x + dx[i];
            
            //벗어나는거 예외처리 추가하자
            if(next.y < 0 || next.y >= SIZE 
              || next.x < 0 || next.x >= SIZE)
            {
                continue;
            }
            
            if (board[next.y][next.x] == 1) continue;
       
            next.dir = i;
                       
            if(next.dir == cur.dir || cur.dir == -1)
            {
                next.cost = 100 + cur.cost;
            }
            else
            {
                next.cost = 600 + cur.cost;
            }                
            
            //등호를 써야 한다. 
            if(tmpCost[next.y][next.x] >= next.cost)
            {
                tmpCost[next.y][next.x] = next.cost;
                q.push(next);
            }
            
            
        }
        
        
        
    }
    
    
    
    
}


int solution(vector<vector<int>> board) {
    
    bfs(board);
    
    return answer;
}

-> dfs로 풀어야 한다고 한다..