[2020 카카오 인턴십 코딩테스트] 경주로 건설

분류 

dp, bfs

 

요구사항

경주로를 건설하는 최소 금액 구하기

 

풀이

dp(?) 식으로 접근하고 싶었다.

현재 map에 도달할 수 있는 금액

이전 map에 저장되어 있는 금액 

위 두가지를 비교하여 작다면 큐에 넣어서 탐색을 실시하도록 하였다.

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#include <deque>

using namespace std;
struct go{
	int x;
	int y;
	int z;
	int cost;
};
int dr[4]=  {-1,0,1,0};
int dc[4] = {0,-1,0,1};
int visit[25][25]={0,};
int n,m;
int tempans=25*25*500;
queue<go> q;
bool check(int nowd, int nextd){
	if(nowd==0){
		if(nextd==0 || nextd==2) return true;
		return false;
	}
	else if(nowd==1){
		if(nextd==1 || nextd==3) return true;
		return false;
	}
	else if(nowd==2){
		if(nextd==0 || nextd==2) return true;
		return false;
	}
	else if(nowd==3){
		if(nextd==1 || nextd==3) return true;
		return false;
	}

}

int solution(vector<vector<int>> board) {
    int answer = 0;
	n=board.size();
	m=board[0].size();
	for(int i=0 ; i <board.size() ; i++)
		for(int j=0 ; j <board[0].size() ; j++)
			visit[i][j]=25*25*600;
	for(int i=0 ; i <4 ; i++){
		q.push({0,0,i,0});
	}
	while(!q.empty()){
		int r = q.front().x;
		int c = q.front().y;
		int z = q.front().z;
		int cost= q.front().cost;
		q.pop();

		for(int i=0 ; i<4 ; i++){
			int nr = r+dr[i];
			int nc = c+dc[i];
			if(nr<0 || nc<0 || nr>=n || nc>=m) continue;
			if(board[nr][nc]==1) continue;
			//직선 도로
			if(check(z,i)){
				//계산해보자
				int ncost= cost+100;
				if(ncost <=visit[nr][nc]){
					visit[nr][nc]=ncost;
					q.push({nr,nc,i,ncost});
				}
			}
			//코너도로
			else{
				int ncost= cost+600;
				if(ncost <=visit[nr][nc]){
					visit[nr][nc]=ncost;
					q.push({nr,nc,i,ncost});
				}
			}
		}
	}
    return answer=visit[n-1][m-1];
}