등굣길 42898

문제

접근 방법

처음에는 최단 거리를 구하는 줄 알고 그렇게 코드를 작성했다. 문제를 잘 읽고 해결하는 것이 중요한 것 같다.
여러 경우를 생각해보자.

집	1	1	1
1	2	3	학교(4)

간단한 형태이다. 웅덩이도 없이 가로 4 세로 2 칸으로 만들어진 공간이다. 각 칸에 대해서 갈 수 있는 경우를 작성했다.
오른쪽, 아래로 가는 경우는 1개의 경우이다. 그 사이는 두 경우를 합하면 되는 것이다.
지그재그로 가더라도 결국에는 변의 길이가 같다는 성질을 생각하면 될 것이다.

집	1	1	1
1	웅덩이	1	학교(2)

입출력의 예와 비슷한 형태이다. 이때에도 위, 왼쪽을 더하며 간다.

집	1	1	1
1	웅덩이(0)	0+1	1+1(2)
1	0+1	1+1(2)	학교(4)

웅덩이에 해당하는 부분을 0으로 처리하여서 해결해주면 된다는 것이 도출된다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
long long dp[101][101];
int solution(int m, int n, vector<vector<int>> puddles)
{
    for (auto puddle : puddles)
    {
        dp[puddle[1]][puddle[0]] = -1;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (dp[i][1] != -1)
            dp[i][1] = 1;
        else
            break;
    }
    for (int i = 1; i <= m; ++i)
    {
        if (dp[1][i] != -1)
            dp[1][i] = 1;
        else
            break;
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            if (dp[i][j] != -1)
                dp[i][j] = ((dp[i - 1][j] == -1 ? 0 : dp[i - 1][j]) + (dp[i][j - 1] == -1 ? 0 : dp[i][j - 1])) % 1000000007;
        }
    }
    return dp[n][m];
}

풀이

오른쪽, 아래 방향으로는 1개의 경로밖에 없기에 1로 채워준다. 만약 물이 잠긴 지역이라면 채워주는 것을 멈춘다. (더 이상 갈 수 없으므로)
그런 다음 식을 적용해주면 해결된다.

물이 잠긴 지역의 좌표가 가로, 세로로 주는지 세로, 가로로 주는 지가 확인이 안 돼서 틀렸었다. 반대로 적어주니, 제대로 작동하였다.