[1일 1알고] 경주로 건설

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

프로그래머스

 

일반적인 bfs(다익스트라)에 방향 개념이 더해진 문제입니다.

N자체가 최대 25이기 때문에 꼭 다익스트라를 써서 단축시킬 필요는 없겠네요

 

해당 문제에서 가장 중요한 것은 방향입니다.

같은 위치이더라도 방향에 따라 이후의 비용이 달라질 수 있기 때문에 이에 대한 계산을 별도로 해야합니다.

 

예를 들어 r, c의 위치에서 특정 방향의 cost가 가장 작더라도, 이후의 진행상황에 따라 다른 방향이 더 cost가 적은 길이 될 수 있기 때문에 섵부르게 미리 통합할 수 없습니다.

 

계산 후 도착지인 (N-1, N-1)에서 모든 방향에 대해 최소 비용을 계산하면 이것이 답이 됩니다.

 

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

using namespace std;

// NxN
// 0,0 -> (N-1, N-1)

struct Road
{
    int r, c, dir;
};

int solution(vector<vector<int>> board) {
    int answer = INT_MAX;
    int N = board.size();

    const int INF = INT_MAX;

    // dist[r][c][dir]
    vector<vector<vector<int>>> dist(
        N, vector<vector<int>>(N, vector<int>(4, INF))
    );

    queue<Road> q;
    for (int d = 0; d < 4; ++d) {
        dist[0][0][d] = 0;
        q.push({ 0, 0, d });
    }

    int dr[4] = { -1, 0, 1, 0 };
    int dc[4] = { 0, -1, 0, 1 };

    while (!q.empty())
    {
        auto [r, c, dir] = q.front();
        q.pop();

        for (int d = 0; d < 4; ++d)
        {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr >= 0 && nr < N && nc >= 0 && nc < N && board[nr][nc] == 0)
            {
                int cost;
                if (d == dir)
                {
                    cost = dist[r][c][dir] + 100;
                }
                else
                {
                    cost = dist[r][c][dir] + 100 + 500;
                }

                if (dist[nr][nc][d] < cost)
                    continue;
                dist[nr][nc][d] = cost;
                q.push({ nr, nc, d});
            }
        }
    }

    for (int d = 0; d < 4; ++d)
    {
        answer = min(answer, dist[N - 1][N - 1][d]);
    }
    return answer;
}