[ 프로그래머스 경주로 건설 (Lv3) ] (C++)

프로그래머스의 경주로 건설(Lv3) 문제이다.

 

[ 문제풀이 ]

(0 , 0)에서 (N - 1 , N - 1)로 경주로를 만들면서 갈 때 가장 저렴한 비용으로 경주로를 건설할 때, 그 비용을 구해야 하는 문제이다.

 

#1. 접근 방법

본인은 이 문제를 완전탐색으로 접근해 보았다. 완전탐색 중에서도 너비우선탐색인 BFS 탐색을 이용해서 접근하였다.

(0 , 0)에서 (N - 1 , N - 1)까지 갈 수 있는 경주로를 모두 만들어 본 후에 가장 최저의 비용을 정답으로 채택하는 방식으로 접근하였다.

 

#2. 정보 관리

그럼 완전탐색을 함에 있어서 우리가 알고 있어야 할 정보가 무엇이 있을지 이야기해보자.

가장 먼저 현재의 좌표에 대한 정보가 필요할 것이다. 즉 ! 현재 탐색 중인 (x , y)에 대한 정보가 필요하다.

두 번째로는 '비용' 정보가 필요할 것이다. 우리가 구하고자 하는 것과 가장 밀접한 관계를 가진 정보이기도 하다.

현재 좌표까지 오기 위해서 설치한 경주로의 비용을 알고 있어야 할 것이다.

세 번째로는 '방향' 정보가 필요할 것이다. 방향 정보는 왜 필요한 것일까 ??

바로 직선도로와 코너에 대해서 판별해주기 위해서 필요하다. 자동차의 기존의 방향과 현재 탐색하려는 방향을 비교해서 같다면 이는 직선도로를 의미하는 것이고 그게 아니라면 코너 라는 것을 의미할 것이다.

그리고 이 직선도로와 코너에 따라서 '비용'이 달라질 것이다.

따라서 본인은 이렇게 총 4가지(x좌표 , y좌표 , 비용 , 방향) 정보를 가지고 완전탐색을 진행해 주었다.

 

#3. 탐색 및 정답 도출

완전탐색에서 가장 주의해야 할 부분 중에 하나가 이미 탐색한 정보에 대해서 중복적으로 탐색을 하면 안된다는 것이다.

그렇다면 ! 이 문제에서 "이미 탐색한 정보"를 어떻게 표현할 수 있을까 ??

보통 일반적으로 2차원 맵이 주어졌을 때는 해당 좌표를 기존에 방문한 적이 있는지 없는지를 판단하면서 탐색을 진행해준다.

이 문제에서도 똑같이 적용시키면 될까?? 이 문제에서는 단순히 "방문을 한적이 있는지 없는지"로 판단을 할 수는 없다.

왜냐하면 ! 우리가 구하고자 하는 것이 단순 최단경로가 아닌, "최소비용" 이기 때문이다.

즉 ! 똑같은 좌표를 여러번 탐색을 할 수도 있다는 것이다. 왜냐하면 기존에 (x , y)라는 좌표를 탐색했을 때, (x , y)까지 만드는데 드는 경주로의 비용이 K 원이라고 가정했을 때, 현재 탐색으로 (x , y)까지 만드는데 드는 경주로의 비용이 K원이 더 낮은 가격으로 건설할 수 있다면 이는 더 낮은 가격으로 다시 탐색을 하는 것이 맞기 때문이다.

정말 이해하기 쉬운 하나의 좌표가 있다. 바로 (N - 1, N - 1)이다.

(N - 1, N - 1)을 한번 탐색했다는 이유로 그 이후에 탐색을 더 이상 못하게 하면 아마 제대로된 정답을 구할 수 없을 것이다.

우리는 (N - 1, N - 1)로 갈 수 있는 모든 경로를 만들어 본 후에, 최단경로가 아닌 "최소비용" 을 구해야 한다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
struct ROAD
{
    int x;
    int y;
    int Cost;
    int Dir;
};
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
int solution(vector<vector<int>> board) 
{
    vector<vector<int>> Cost;
    Cost.resize(board.size(), vector<int>(board.size(), 2e9));
    queue<ROAD> Q;
    Q.push({ 0, 0, 0, -1 });
    Cost[0][0] = 0;
 
    int answer = 2e9;
    while (Q.empty() == 0)
    {
        int x = Q.front().x;
        int y = Q.front().y;
        int Pay = Q.front().Cost;
        int Dir = Q.front().Dir;
        Q.pop();
 
        if (x == board.size() - 1 && y == board.size() - 1)
        {
            answer = Min(answer, Cost[x][y]);
            continue;
        }
        
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < board.size() && ny < board.size())
            {
                if (board[nx][ny] == 1) continue;
 
                int nPay;
                if (Dir == -1 || Dir == i) nPay = Pay + 100;
                else nPay = Pay + 600;
                
                if (Cost[nx][ny] >= nPay)
                {
                    Cost[nx][ny] = nPay;
                    Q.push({ nx, ny, nPay, i });
                }
            }
        }
    }
    return answer;
}