[DFS] 경주로 건설 - 2020 카카오 인턴십

해결 방법

DP와 DFS를 병행하여 해결하였으며, DP없이 DFS로만 해결하면 시간초과가 나온다.

이 문제의 경우에는 나아가는 방향이 직진인지 코너인지를 판별하여 100 또는 600(코너 비용 500추가)을 더해야 한다.

이를 위해서는 다음 DFS 재귀함수를 반복할 때 현재의 진행 방향이 전달되어야 한다. 이 때, 동서남북을 일일이 가려낼 필요는 없으며 가로(동서) 방향과 세로(남북) 방향만 알면 된다.

연산시간 절약을 위해 현재 dfs 재귀에서 cost가 answer값을 넘는다면 더 이상 dfs 재귀를 수행하지 않도록 했다. 그리고 진행 칸에 대한 최소 비용이 갱신되지 않았다면 이 역시 더 이상 dfs 재귀를 수행하지 않도록 하되, 직선 도로와 코너 건설 비용의 차이인 500이 있을 수 있다는 사실을 반영했다. 쉽게 말하면, 칸에 도달했을 때 카트는 세로 방향일 수도 있고 수평 방향일 수도 있기 때문에 이후에 같은 칸으로 전진하더라도 직선 도로의 경우에는 100을 더해야 하고 코너의 경우에는 600을 더해야 하기 때문에 이 차이를 반영하지 않으면 안된다.

 

 

소스 코드

#include <vector>
using namespace std;
int _board[25][25]; // board 복사
int board_cost[25][25]; // dp 배열
bool visited[25][25]; // 중복 방문 확인
int x[4]={0, 0, 1, -1};
int y[4]={1, -1, 0, 0};
int board_size;
int answer=999999999;

struct kart {
    int x, y;
    int d; // 방향 0: 무방향, 1: 가로 방향, 2: 세로 방향
    int c; // 비용
};

int findd(int x, int y){
    if(y!=0) return 1; // 가로 방향
    if(x!=0) return 2; // 세로 방향
}

void dfs(kart k){
    int cost=100;
    if(k.x==board_size-1&&k.y==board_size-1){
        answer=min(answer, k.c);
        return;
    }
    for(int i=0;i<4;i++){
        if(k.x+x[i]<0||k.x+x[i]>=board_size||k.y+y[i]<0||k.y+y[i]>=board_size) continue;
        if(_board[k.x+x[i]][k.y+y[i]]) continue; // 벽
        if(visited[k.x+x[i]][k.y+y[i]]) continue; // 중복 방문
        if(k.d==1){ // 좌, 우에서 오는 카트
            if(x[i]!=0) cost=600; // 상, 하 이동
            else cost=100; // 직진
        }
        else if(k.d==2){ // 상, 하에서 오는 카트
            if(y[i]!=0) cost=600; // 좌, 우 이동
            else cost=100; // 직진
        }
        if(k.c+cost<answer&&k.c+cost<=board_cost[k.x+x[i]][k.y+y[i]]+500) { // 직선 도로와 코너 건설비용의 차이인 500을 반영
            board_cost[k.x+x[i]][k.y+y[i]]=k.c+cost;
            visited[k.x+x[i]][k.y+y[i]]=true;
            dfs({k.x+x[i], k.y+y[i], findd(x[i], y[i]), k.c+cost});
            visited[k.x+x[i]][k.y+y[i]]=false;
        }
    }
}

int solution(vector<vector<int>> board) {
    board_size=board.size();
    for(int i=0;i<board_size;i++){
        for(int j=0;j<board_size;j++){
            board_cost[i][j]=999999999;
            _board[i][j]=board[i][j];
        }
    }
    visited[0][0]=true;
    dfs({0, 0, 0, 0});
    return answer;
}

 

테스트 케이스 25개 모두 정답