프로그래머스 - 경주로 건설 - C++
https://programmers.co.kr/learn/courses/30/lessons/67259
문제설명
- 시작지점부터 목표지점까지 도로를 건설할 때 최소비용을 return하는 문제이다.
- 직진도로는 100원, 코너는 600원의 비용이 발생한다.
접근 방법
-
먼저 BFS를 기반으로 접근 해 보았다.
(DFS로 접근을 하려 해봤지만 인터넷에서 시간초과가 뜬다는걸 봤음...) -
기존의 BFS와 차이점은
- 1.cost
가 직진일 때와 코너일 때 다르게 적용되는 점
- 2. 방문한 도로이더라도cost
가 더 작은 루트를 찾으면 갱신해줘야 하는점 -
위 두가지 차이점을 적용하면 문제 해결이 가능하다.
-
따라서
- 1.bool ch[30][30]
변수가 이미 체크 돼있더라도 같은 지점에서,int cost[30][30]
의 값보다new cost
가 작거나 같으면 한번 더 queue에 넣어준다.head
의 값을 2로 나눈 몫과dx
,dy
의 인덱스 값 2로 나눈 몫이 같다면 같은방향으로 생각한다. 이건 코드를 직접보면 이해가 더 잘 될것이다.
풀이
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct Car{
int x;int y;int cost;int head;
};
bool ch[30][30]; // 방문 변수
bool map[30][30]; // 도로 상태
int Cost[30][30]; // 비용 변수
int n,minC = 200000000;
// 각 구간에서 변화 값
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
void bfs(Car start){
queue<Car> q;
q.push(start);
ch[start.x][start.y] = true;
while(!q.empty()){
Car a = q.front();
q.pop();
if(a.x==n-1&&a.y==n-1){ // 목표 지점일 때 값 갱신
if(minC>a.cost) minC = a.cost;
continue;
}
for(int i=0;i<4;i++){
int nx = a.x+dx[i];
int ny = a.y+dy[i];
if(nx<0)continue;
if(nx>=n)continue;
if(ny<0)continue;
if(ny>=n)continue;
if(map[nx][ny] == 1)continue; // queue 삽입 조건
int nc = a.cost;
if((a.head)/2 == i/2) nc+=100; // 같은 방향이면
else nc+=600;
if(!ch[nx][ny] || Cost[nx][ny]>=nc){
ch[nx][ny]=true;
q.push({nx,ny,nc,i}); // i는 방향 변수로 0~1은 x방향 2~3은 y방향
Cost[nx][ny] = nc;
}
}
}
}
int solution(vector<vector<int>> board) {
int answer = 0;
n = board.size();
for(int i =0;i<n;i++){
for(int j=0;j<n;j++){
map[i][j] = board[i][j];
}
}
bfs({0,0,0,6}); // 처음에는 무조건 방향이 다르도록 설정하여
answer = minC - 500; // 여기서 600-100을 빼주면 된다.
return answer;
}
결과
Author And Source
이 문제에 관하여(프로그래머스 - 경주로 건설 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@961230/프로그래머스-경주로-건설-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)