2020 카카오 인턴십-경주로 건설-C++

BFS + 3차원배열을 활용하는문제
문제 바로가기

문제 핵심
1. BFS인데 visited 배열을 사용하지 않아, 한번 방문한 노드를 다시 방문가능하게 할것(최소비용을 계산하기위해)
2. 다시 방문하는 기준은 방문할 노드보다 최소비용이 더 작으면 queue에 삽입가능
3. 3차원배열

처음에는 2차원배열로 문제를 풀었는데 25번 테스트 케이스만 틀렸음.
그이유는 항상 최소값으로 노드를 갱신하다 하더라도, 최소의 결과를 내지 않는다는거임

이말이 뭔지 그림으로 설명하면,

최소비용으로 갱신을 한다면 초록색 형광펜을 칠한 노드에 2100이 들어갈것이다. 왜냐하면 동쪽으로 출발해서 아래로 내려온 경로는 2400이니까 말이다.
그러면 답이 3300이 나올텐데, 정답은 3000이다.

이렇게 결과가 나오는 이유는 바로 방향을 고려해야하기 때문이다.
그래서, 2차원배열이 아니라 3차원 배열로 만들어서,
map위에 조그만한 사각형 노드처럼 하나의 노드에는 4방향의 cost를 저장하여서 3,4 위치의 배열에는 왼쪽에서 오른쪽으로 왔을때, 위에서 아래로 내려왔을때의 cost를 전부 저장해서 계산해야한다.

그리고 최종정답은 cost[m_size-1][m_size-1][0,1,2,3]중에서 가장 작은것을 선택하면된다.

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

struct Data{
    int x;
    int y;
    int direction;
    int s;
    int c;
};

struct sc{
    int s;
    int c;
};

int m_size=0;
int map[25][25];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
sc cost[25][25][4];
queue <Data> q;
void BFS(){
    Data d = {0,0,-1,0,0};
    q.push(d);
    while(!q.empty()){
        Data d = q.front();
        q.pop();
        int x = d.x;
        int y = d.y;
        int direction = d.direction;
        int s = d.s;
        int c = d.c;
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx>=0 && nx<m_size && ny>=0 && ny<m_size && map[nx][ny]!=1){
                int ns =0; int nc=0; int nd=0;
                //처음 시작점에서 오른쪽,아래이동
                if(direction==-1 && i==0){
                    nd=0;
                    ns=s+1;
                    nc=c;
                }else if(direction==-1 && i==1){
                    nd=1;
                    ns=s+1;
                    nc=c;
                }else{
                    //현재 이동방향과 다르면 무조건 코너처리,이전 좌표로 이동해도 ns가 늘어나서 어차피 큐에 안드감
                    if(direction!=i){
                        nd=i;
                        ns=s+1;
                        nc=c+1;
                    }else{
                        //직선처리
                        nd=i;
                        ns=s+1;
                        nc=c;
                    }
                }
                //3,4는 아래로 내려온 nd 1
                //3,4는 왼쪽에서 오른쪽으로 이동한 nd 0 
                //이 두개가 저장되어있음
                sc temp = cost[nx][ny][nd];
                int n_s = temp.s;
                int n_c = temp.c;
                
                int n_total = n_s*100+n_c*500;
                int c_total = ns*100+nc*500;
                if(c_total<=n_total){
                    Data d = {nx,ny,nd,ns,nc};
                    sc t ={ns,nc};
                    //cost갱신
                    cost[nx][ny][nd]=t;
                    q.push(d);
                }
            }
        }
    }
}

int solution(vector<vector<int>> board) {

    m_size=board.size();
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            map[i][j] = board[i][j];
        }
    }
    
    sc t ={1000,10000};
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            for(int k=0;k<4;k++){
                cost[i][j][k] = t;
            }
        }
    }
    sc tt ={0,0};
    cost[0][0][0]=tt;
    cost[0][0][1]=tt;
    cost[0][0][2]=tt;
    cost[0][0][3]=tt;
    BFS();
    int ttt=100000000;
    for(int i=0;i<4;i++){
        sc answer = cost[m_size-1][m_size-1][i];
        int t=answer.s*100+answer.c*500;
        if(ttt>t){
            ttt=t;
        }
    }
    return ttt;
}