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

문제 링크: programmers.co.kr/learn/courses/30/lessons/67259

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

1. 주의할 점

- BFS를 통해 해결한다

- Check[][][]를 통해 해당지점에 특정 방향에서 왔을때의 최소비용을 저장한다

- 코너가 생길 경우, 코너+직선이다

2. 구현

- Check[][][] 배열을 전부 MAX로 초기화한다

- BFS() 함수를 통해 조건 만족시 이동하도록 한다

- Check[y][x][dir]: (y,x)에 dir방향에서 접근했을 때 최소값

- 방향이 바뀔 경우, 코너 생성으로 비용은 코너+직선인 600이다

#define MAX 987654321
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct info{
    int y,x,cost,dir;
};
info tmp;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int arr[25][25];
int check[25][25][4];
int num,result=MAX;

void bfs(){
    queue<info> q;
    for(int i=0;i<4;i++){
        q.push({0,0,0,i});
        check[0][0][i]=0;
    }
    while(!q.empty()){
        int cx = q.front().x;
        int cy = q.front().y;
        int cc = q.front().cost;
        int cd = q.front().dir;
        q.pop();
        if(check[cy][cx][cd]!=cc) continue;
        if(cy==num-1 && cx==num-1){
            result = min(result,cc);
            continue;
        }
        for(int i=0;i<4;i++){
            int nx = cx+dx[i];
            int ny = cy+dy[i];
            if(nx>=0 && ny>=0 && nx<num && ny<num && arr[ny][nx]==0){
                int nextCost=100;       //직선
                if(cd!=i) nextCost=600; //코너
                if(check[ny][nx][i] > cc + nextCost){
                    check[ny][nx][i] = cc + nextCost;
                    q.push({ny,nx,cc + nextCost,i});
                }
            }
        }
    }
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    num = board.size();
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++){
            arr[i][j]=board[i][j];
            for(int k=0;k<4;k++)
                check[i][j][k]=MAX;
        }
    bfs();
    return answer=result;
}