프로그래머스) Lv3 - 경주로 건설 [2020 카카오 인턴십]

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

코딩테스트 연습 - 경주로 건설

BFS로 격자에 4개의 진행방향마다 최소값을 갱신하여 풀이하였습니다.

---

C++ 소스 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int dx[] = {0,0,-1,1}, dy[]={-1,1,0,0};
struct path {
    int x,y,z;
};
int solution(vector<vector<int>> board) {
    int answer;
    int bSize = (int)board.size();
    int dist[26][26][4];
    fill(&dist[0][0][0], &dist[25][25][2]+1, 1000000);
    queue<path> q;
    q.push({0,0,1});
    q.push({0,0,3});
    dist[0][0][1]=0;
    dist[0][0][3]=0;
    while(!q.empty()){
        int x = q.front().x, y = q.front().y;
        int z = q.front().z; q.pop();
        int lastcost = dist[x][y][z];
        for(int k=0;k<4;k++){
            int nx = x+dx[k], ny= y+dy[k];
            if (nx <0 || nx >= bSize || ny <0 || ny>=bSize || board[nx][ny]) continue;
            if (k==z){ //같은 방향으로 이동할 때
                if (dist[nx][ny][k]> lastcost+100){
                    dist[nx][ny][k] =lastcost+100;
                    q.push({nx,ny,k});
                }
            }else if (dist[nx][ny][k]> lastcost+600){ //다른 방향으로 이동할때 코너 비용 추가
                    dist[nx][ny][k] = lastcost+600;
                    q.push({nx,ny,k});
                }
        }
    }
    answer = min(dist[bSize-1][bSize-1][1],dist[bSize-1][bSize-1][3]);
    return answer;
}