프로그래머스 - 경주로 건설 - 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에 넣어준다.

  • 2. 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;
}

결과