2020 KAKAO 카카오 인턴쉽 경주로 건설

https://programmers.co.kr/learn/courses/30/lessons/67259?language=cpp 

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

 

처음에는 DFS로만 접근하여 문제를 풀어서 맞췄다. 하지만, 현재 위치에서의 탐색순서를 바꾸면 24번이 틀린다고 나온다.

곰곰히 생각해보니, 특정 cell에 도착한 뒤 방향에 따라서 이후 값이 변경될 수 있다고 생각했다.
예를 들면 (0,0) -> (0,1) -> (1,1) 과 (0,0) -> (1,0) -> (1,1) 은 (1,1) 까지 도달하는 cost는 같지만, 방향이 다르기 때문에 이후 값들이 달라질 수 있다. 벽이 있으면 그럴 확률이 더 높아진다.

따라서 visited에 방향까지 추가하여 DFS를 실행하였다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int visited[25][25][4];
int n;
const int INF = 0xfffffff;

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

void dfs(int nowr, int nowc, int nowd, vector<vector<int>>& board){
    
    for(int i=0;i<4;i++){
        int nextr = nowr + dr[i];
        int nextc = nowc + dc[i];
        if(nextr >= n || nextc >= n || nextr < 0 || nextc < 0) continue;
        if(board[nextr][nextc] == 1) continue;
        if((nowd+2)%4 == i) continue;
        int addCost = (i == nowd) ? 100 : 600;
        int nextCost = visited[nowr][nowc][nowd] + addCost;
        if(visited[nextr][nextc][i] > nextCost){
            visited[nextr][nextc][i] = nextCost;
            dfs(nextr, nextc, i, board);
        }
    }
    
}

int solution(vector<vector<int>> board) {
    n = board.size();
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<4;k++) visited[i][j][k] = INF;
        }
    }
    visited[0][0][0] = 0;
    visited[0][0][1] = 0;
    dfs(0,0,0, board);
    dfs(0,0,1, board);
    
    return *min_element(visited[n-1][n-1], visited[n-1][n-1]+4);
}