(프로그래머스 c++ KAKAO)경주로 건설

programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

 

BFS와 DP를 활용한다.

 

BFS로 길을 탐색하면서 다음에 이동할 위치의 비용이 현재 비용 + 건설 도로 비용보다 크면 비용을 바꿔주면서 진행한다.

 

N = 보드의 크기.

directX, directY = 상하좌우 이동 방향 배열

q = ({이동한 위치 x, 이동한 위치 y}, {현재 위치로 오게 된 방향, 현재 위치의 비용}) 을 나타낸다.

(방향 인덱스는 0 1 2 3 차례대로 상 하 좌 우를 나타내며 4는 오른쪽 또는 아래쪽으로 이동하기 때문에 아무 상관이 없다)

 

1. 시작은 ({{0, 0},{4, 0}})으로 한다. 

2. board[0][0] = 1로 하여 다시 못돌아오게 방지.

3-1 큐에서 하나씩 pop하여 값을 가져온다.

3-2 만약 x, y가 N - 1이라면 도착이니까 비용이 가장 적은 값을 answer에 넣어준다.

3-3 도착 지점이 아니라면 BFS 시작.

3-4 현재 위치까지 어느 방향으로 왔는지 검사하여 코너가 예상되면 600원을 더하고, 직선 도로면 100원만 더해준다.

3-5 다음 이동할 위치의 비용이 0이거나 (현재 비용 + 추가 도로 비용)보다 크다면 값을 바꿔주고 큐에 삽입.

3-6 큐가 빌 때까지 반복.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <climits>

using namespace std;

int solution(vector<vector<int>> board) {
    //직선 = 100원, 코너 = 500원
    int answer = INT_MAX;
    int N = board.size();
    int directX[4] = {-1, 1, 0, 0};
    int directY[4] = {0, 0, -1, 1};
    queue<pair<pair<int, int>, pair<int, int>>> q;
    
    q.push({{0, 0}, {4, 0}});
    board[0][0] = 1;
    
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int dir = q.front().second.first;
        int currentCost = q.front().second.second;

        q.pop();

        if(x == N - 1 && y == N - 1){
            answer = answer < currentCost ? answer : currentCost;
            continue;
        }

        for(int j = 0; j < 4; j++){
            int nx = x + directX[j];
            int ny = y + directY[j];
            int add = 100;

            if(nx >= 0 && nx < N && ny >= 0 && ny < N && board[nx][ny] != 1){
                if(dir == 0 || dir == 1){
                    if(!(j == 0 || j == 1)){
                        add += 500;
                    }
                }
                else if(dir == 2 || dir == 3){
                    if(!(j == 2 || j == 3)){
                        add += 500;
                    }
                }
                
                if(board[nx][ny] == 0 || board[nx][ny] >= currentCost + add){
                    board[nx][ny] = currentCost + add;
                    q.push({{nx, ny}, {j, currentCost + add}});    
                }    
            }
        }
    }
    
    return answer;
}