[C++] Programmers Lv. 3 "경주로 건설"

🔵 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

 

🔵 문제 접근

가중치(이동 비용)가 있는 그래프 + 최소 비용 계산 문제이다.

따라서 다익스트라 개념 + BFS를 조합하여 풀이한다.

 

우선 순위 큐를 사용하여 현재까지의 최소 비용 순으로 노드를 탐색한다.

비용이 작은 경로부터 탐색하며, 더 효율적으로 최단 경로를 찾는다.

 

여기서 중요한 점은 3차원 배열(x 위치, y 위치, 방향)을 활용해 cost를 저장한다는 것이다.

단순히 2차원 배열(x 위치, y 위치)만을 이용하여 cost를 저장하면 어떤 문제가 발생하는지 예를 들어 알아보자.

 

(2, 2) 위치에 방향 ➡️로 도착한 비용이 900이고, (2, 2) 위치에 방향 ⬇️로 도착한 비용이 1100이라고 가정해 보자.

만약 단순히 2차원 배열 cost[2][2] = 900만 저장한다면, ⬇️ 방향에서 도착하는 경로가 나중에 더 유리할 경우를 무시하게 된다.

(⬇️ 방향으로 (2, 2)에 도착한 경로가 나중에 커브가 적게 생길 가능성이 있음.)

 

따라서 비용 저장과 방문 기록은 방향별로 따로 해야 정확한 최적 경로를 찾을 수 있다. 

 

🔵 전체 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

// 상하좌우
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ans = 987654321;

struct State
{
    int x, y, dir, cost;
    bool operator>(const State& a) const
    {
        return cost > a.cost;
    }
};

int solution(vector<vector<int>> board) 
{
    int max = board.size();
    vector<vector<vector<int>>> cost(max, vector<vector<int>>(max, vector<int>(4, 987654321)));
    priority_queue<State, vector<State>, greater<State>> pq;
    
    // 제일 처음은 방향이 없으므로 -1을 push
    pq.push({ 0, 0, -1, 0 });

    // 제일 처음 위치의 모든 방향은 cost가 0
    for (int d = 0; d < 4; d++)
        cost[0][0][d] = 0;

    while (!pq.empty())
    {
        State cur = pq.top();
        pq.pop();

        if (cur.x == max - 1 && cur.y == max - 1)
            return cur.cost;

        for (int i = 0; i < 4; i++)
        {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx < 0 || ny < 0 || nx >= max || ny >= max) continue;
            if (board[nx][ny] == 1) continue;

            int newCost = cur.cost + 100;
            if (cur.dir != -1 && cur.dir != i) newCost += 500;

            if (cost[nx][ny][i] > newCost)
            {
                cost[nx][ny][i] = newCost;
                pq.push({ nx, ny, i, newCost });
            }
        }
    }

    return 0;
}

 

🔵 문법 설명 

struct State
{
    int x, y, dir, cost;
    bool operator>(const State& a) const
    {
        return cost > a.cost;
    }
};

// priority_queue<자료형, 컨테이너, 비교함수>
priority_queue<State, vector<State>, greater<State>> pq;

 

우선 순위 큐는 기본적으로 max-heap 구조이다.

cost가 작은 값이 먼저 나오게 하려면 greater<>를 이용해서 내부 정렬 기준을 반대로 바꿔줘야 한다.

내부적으로 greater<>()(a, b) -> a>b인지를 확인해서 작은 값이 우선된다. (큰값 우선은 a < b임)

하지만 내가 정의한 State 구조체에는 operator>가 정의되어 있지 않아 비교할 수 없다.

따라서 직접 정의해줘야 한다.

 

🔵 시간 복잡도

BFS는 모든 위치를 한번씩 탐색하므로 O(N^2)이다.