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

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

프로그래머스

풀이

완전 탐색을 해야 하기 때문에 BFS로 해결하려 했다.

3차원 체크 배열 탐색이 정답이 될 것 같았으나, 2차원도 가능해 보여서 시도해봤는데 25번 테스트 케이스가 오답이다.

2차원 배열의 경우, 만나는 지점에서 1번째 경로보다 2번째 경로 비용이 크면 2번째 경로를 다시 큐에 넣지 않는데, 이 때, 다음 지점을 탐색할 때 1번 경로의 비용이 2번 경로의 비용보다 커지는 케이스이다. 

ex) 만나는 지점의 비용 - 1번 경로: 2000, 2번 경로: 2200

      다음 지점의 비용 - 1번 경로: 2600(직각의 경우), 2번 경로 : 2300(직진)

 

따라서, 3차원 체크 배열로 2000과 2200 비용 모두 기록해야 한다. 하나의 지점에 도달 가능한 경로는 상하좌우 4가지 이므로 visited[행][열][4]를 사용해서 거리를 체크해준다. 이 때, vistied[nr][nc][i] > cost일 경우만 다시 큐에 넣어 같은 방향으로의 중복 방문을 막아준다 (지점은 중복 방문 가능). 

아래 예시에서 (1, 1) 지점을 방문하는 경우는 700 또는 900인데, 900은 기존보다 크므로 큐에 다시 넣지 않는다. 

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int dr[4]={0, 1, 0, -1};
int dc[4]={1, 0, -1, 0};

struct Info{
    int row, col, dir, cost;
    Info (int a, int b, int c, int d){
        row=a;
        col=b;
        dir=c;
        cost=d;
    }
};

int solution(vector<vector<int>> board) {
    int answer = 2147000000;
    queue<Info> q;
    q.push(Info(0, 0, 0, 0));
    q.push(Info(0, 0, 1, 0));
    vector<vector<vector<int>>> visited(board.size(), 
                                vector<vector<int>> (board.size(), 
                                vector<int> (board.size(), 2147000000)));
    
    while (!q.empty()){
        Info v = q.front();
        q.pop();
        
        for (int i=0; i<4; i++){
            int nr = v.row+dr[i];
            int nc = v.col+dc[i];
            if (nr<0 || nr>(board.size()-1) || nc<0 || nc>(board.size()-1)) continue;
            if (board[nr][nc]==1) continue;
            int cost=0;
            if (v.cost){
                if (i!=v.dir){
                    cost=v.cost+600;
                }
                else {
                    cost=v.cost+100;
                }
            }
            else{
                // 출발
                cost = 100;
            }
            
            if (visited[nr][nc][i]>cost){
                visited[nr][nc][i]=cost;
                q.push(Info(nr, nc, i, cost));
            }
            
        }
    }
    for (int i=0; i<4; i++){ 
        if (answer > visited[board.size()-1][board.size()-1][i])
            answer = visited[board.size()-1][board.size()-1][i];
    }
    return answer;
}