Level 3. 경주로 건설

Level 3. 경주로 건설

 

 

생각보다 엄청 쉬운 DFS 문제였는데, 길이가 아니라 비용이 추가되어 있어 좀 헷갈렸다.

 

단순 방문 여부를 저장하는 visited 배열로는 안 되고, 자신에게 온 4개 방향마다 비용을 저장해야 한다.

• 비용이 양수이므로, 이전보다 큰지를 통해 재방문 여부를 확인할 수 있는 게 핵심이다.

 

다음 칸으로 진행할 때 진행 방향을 전달하고, 왔던 방향과 같으면 100을, 다르면 600을 더해 전달하면 된다.

• 왔던 방향으로 다시 돌아가는 경우에도 600을 전달하면 알아서 재방문으로 처리되므로 문제 없다.

 

DFS 문제일 것이라고 생각은 했지만, 이렇게 단순무식하게 모든 경우의 수를 탐색해야 하는지는 몰랐다.

 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

enum class DIR
{
    DOWN,
    RIGHT,
    UP,
    LEFT
};

int rDFS(unsigned r, unsigned c, DIR dir, int cur_cost, vector<vector<int>>& board, vector<vector<unordered_map<DIR, int>>>& cost)
{
    size_t n = board.size();

    if (n <= r || n <= c || board[r][c] == 1 || cost[r][c][dir] <= cur_cost)
        return INT_MAX;

    cost[r][c][dir] = cur_cost;

    if (r == n - 1 && c == n - 1)
        return cur_cost;

    int result = INT_MAX;
    unordered_map<DIR, vector<int>> umap = {{DIR::DOWN, {1, 0}}, {DIR::RIGHT, {0, 1}}, {DIR::UP, {-1, 0}}, {DIR::LEFT, {0, -1}}};

    for (auto& pr : umap)
    {
        DIR nextDir = pr.first;
        int dr = pr.second[0];
        int dc = pr.second[1];

        result = min(result, rDFS(r + dr, c + dc, nextDir, cur_cost + (dir == nextDir ? 100 : 600), board, cost));
    }

    return result;
}

int solution(vector<vector<int>> board)
{
    size_t n = board.size();
    vector<vector<unordered_map<DIR, int>>> cost(n, vector<unordered_map<DIR, int>>(n,
        {{DIR::DOWN,  INT_MAX},
         {DIR::RIGHT, INT_MAX},
         {DIR::UP,    INT_MAX},
         {DIR::LEFT,  INT_MAX}}
    ));

    return min(rDFS(0, 0, DIR::DOWN, 0, board, cost), rDFS(0, 0, DIR::RIGHT, 0, board, cost));
}