알고리즘
경주로 건설 - 카카오 2020 C++ DFS 코딩테스트 풀이
sunggook lee
2020. 9. 11. 16:29
다들 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;
}