경주로 건설 - 카카오 2020 C++ DFS 코딩테스트 풀이

다들 BFS풀고 공식해설도 BFS로 풀었다.

 

BFS로 풀든 DFS로 풀든 상관 없지만 핵심은 완전탐색 과 메모이제이션 이 있어야 시간초과가 나지 않고 정답을 맞출수있다.

 

완전탐색이라는 방향에서 BFS나 DFS어느것으로 풀어도되는데 많은 블로그에서 DFS로 풀면 틀린다는 듯이 말을 해서 풀이를 올리게 되었다. 충분히 짧은 시간내에 정답이 가능하다.

 

핵심은 cost배열(메모이제이션) 에 최소비용을 계속 갱신해주고 이 최소비용보다 높다면 그 지점으로 이어지는 경로자체를 return시키는 것이다.

 

#include <string>
#include <vector>
#include <iostream>
int dr[4]={0,1,0,-1};
int dc[4]={1,0,-1,0};
int visited[30][30]={0,};
int cost[30][30]={0,};
using namespace std;
vector<vector<int>> tboard;
int n;
int st=0; int co=0;
int sum=0;
int minv=2100000000;
int tsum;
void dfs(int r,int c,int d,int tsum) {
    
    if(cost[r][c]!=0 && (tsum>cost[r][c]) ) return;
    if(tsum<=cost[r][c]) cost[r][c]=tsum;
    
    if(r==n-1 && c==n-1)
    {
        if(minv>tsum) 
            minv=tsum;
        return;
    }
    
    for(int i=0;i<4;i++)
    {
        int nr=r+dr[i];
        int nc=c+dc[i];
        if((nr>=0 && nr <=n-1) && (nc>=0 && nc<=n-1))
        if(tboard[nr][nc]!=1 && visited[nr][nc]==0)
        {
            visited[nr][nc]=1;
           if(d==i) {
            dfs(nr,nc,d,tsum+100);
           }
            else {
                if(!(r==0 && c==0))
                 tsum+=500;
                dfs(nr,nc,i,tsum+100);
                if(!(r==0 && c==0))
                    tsum-=500;
            }
            visited[nr][nc]=0;
           
        }
    }
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    tboard=board;
    n=board.size();
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cost[i][j]=2100000000;
    visited[0][0]=1;
    dfs(0,0,0,0);
   
    answer=minv;
    return answer;
}