Level 2. 게임 맵 최단거리

Level 2. 게임 맵 최단거리

 

 

처음엔 DFS를 시도해 시간 초과가 발생했다.

 

내가 왔던 방향이 아닌 방향으로 계속 진행하면서 최소 비용을 갱신하는 방식이다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

enum class DIR
{
    Up    = 1,
    Down  = 2,
    Left  = 4,
    Right = 8
};

void rDFS(vector<vector<int>>& maps, int i, int j, int from, int cost)
{
    int n = maps.size(), m = maps.front().size();

    if (i < 0 || n <= i || j < 0 || m <= j || maps[i][j] == 0 || maps[i][j] <= cost)
        return;

    maps[i][j] = cost;

    if (int(DIR::Up) & ~from) rDFS(maps, i - 1, j, int(DIR::Down), cost + 1);
    if (int(DIR::Down) & ~from) rDFS(maps, i + 1, j, int(DIR::Up), cost + 1);
    if (int(DIR::Left) & ~from) rDFS(maps, i, j - 1, int(DIR::Right), cost + 1);
    if (int(DIR::Right) & ~from) rDFS(maps, i, j + 1, int(DIR::Left), cost + 1);
}

int solution(vector<vector<int>> maps)
{
    for_each(maps.begin(), maps.end(), [](vector<int>& v) { replace(v.begin(), v.end(), 1, INT_MAX); });

    rDFS(maps, 0, 0, int(DIR::Up) | int(DIR::Left), 1);

    return (maps.back().back() == INT_MAX) ? -1 : maps.back().back();
}

 

생각해보니 정석적인 BFS 문제였다..

 

오랜만에 BFS를 풀다 보니 큐를 이용해 비용이 낮은 원소부터 순차적으로 처리한다는 걸 깜빡하고 있었다..

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct st
{
    int i;
    int j;
    int cost;
};

int solution(vector<vector<int>> maps)
{
    queue<st> que;
    que.emplace(st{0, 0, 1});
    int n = maps.size() - 1, m = maps.front().size() - 1;

    while (!que.empty())
    {
        st s = que.front(); que.pop();

        if (s.i < 0 || n < s.i || s.j < 0 || m < s.j || maps[s.i][s.j] == 0)
            continue;
        else if (s.i == n && s.j == m)
            return s.cost;

        maps[s.i][s.j] = 0;

        que.emplace(st{s.i - 1, s.j, s.cost + 1});
        que.emplace(st{s.i + 1, s.j, s.cost + 1});
        que.emplace(st{s.i, s.j - 1, s.cost + 1});
        que.emplace(st{s.i, s.j + 1, s.cost + 1});
    }

    return -1;
}