Level 3. 등굣길

Level 3. 등굣길

 

 

BFS가 가물가물해서 BFS로 풀어봤더니 시간 초과가 발생했다.

 

최단 거리순으로 확인하기 때문에, 최초 최단거리를 넘어서는 순간부터는 확인하지 않아도 된다.

 

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

using namespace std;

struct point
{
    int dist;
    int x;
    int y;
};

int solution(int m, int n, vector<vector<int>> puddles)
{
    int answer = 0;
    int minDist = 0;
    int dx[] = {1, 0}, dy[] = {0, 1};
    
    queue<point> que;
    vector<vector<bool>> map(n, vector<bool>(m, true));

    for (vector<int>& puddle : puddles)
        map[puddle[1] - 1][puddle[0] - 1] = false;

    --m, --n;
    que.emplace(point{0, 0, 0});

    while (!que.empty())
    {
        point p = que.front();
        que.pop();

        if (0 < minDist && minDist < p.dist)
            break;

        if (p.x == m && p.y == n && minDist == 0)
            minDist = p.dist;

        if (p.x == m && p.y == n && p.dist == minDist)
            answer = (answer + 1) % 1'000'000'007;

        for (int i = 0; i < 2; ++i)
        {
            int x = p.x + dx[i];
            int y = p.y + dy[i];

            if (x <= m && y <= n && map[y][x])
                que.emplace(point{p.dist + 1, x, y});
        }
    }

    return answer;
}

 

출제 의도대로 DP로 풀었다.

 

옆이나 위로부터 값을 채워가는 형태에서는 추가 패딩을 집어넣는 것이 편하다.

 

#include <iostream>
#include <vector>

#define PUDDLE -1

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles)
{
    vector<vector<int>> map(n + 1, vector<int>(m + 1, 0));

    for (vector<int>& puddle : puddles)
        map[puddle[1]][puddle[0]] = PUDDLE;

    map[0][1] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (map[i][j] != PUDDLE)
                map[i][j] = ((map[i - 1][j] != PUDDLE ? map[i - 1][j] : 0) + (map[i][j - 1] != PUDDLE ? map[i][j - 1] : 0)) % 1'000'000'007;

    return map[n][m];
}

 

좀 더 깔끔한 풀이다.

 

#include <iostream>
#include <vector>

#define PUDDLE -1

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles)
{
    vector<vector<int>> map(n + 1, vector<int>(m + 1, 0));

    for (vector<int>& puddle : puddles)
        map[puddle[1]][puddle[0]] = PUDDLE;

    map[0][1] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (map[i][j] == PUDDLE)
                map[i][j] = 0;
            else
                map[i][j] = (map[i - 1][j] + map[i][j - 1]) % 1'000'000'007;

    return map[n][m];
}