🖊️ 문제

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

---

🖊️ 풀이

일단,, 못풀겠어서 서치해보고 최단거리 구하는 알고리즘을 습득하고, 다시 풀었다.

일단 기본적으로 시작점부터 끝까지 도달하는 알고리즘 중에서,
아래 or 오른쪽 으로만 가는 경우의 수는 간단하다.

이런 상황에서

way[x][y] = way[x-1][y] + way[x][y-1];
이렇게..

물에 빠진 상황에서는 X.
왼쪽까지의 최소 경우의 수 + 위쪽 까지의 최소 경우의 수
그래서 끝까지 가는 경우의 수는 위의 방법으로 구할 수 있다.
그래서 예제의 방법이 4가지 인 것!!

확통할 때 했던 그 간단한 방법..
그래서 이걸 활용해서 문제를 풀건데

물에 잠긴 곳으로 가는 경우의 수는 0이기에
그 곳을 통과하는 경우의 수는 0으로 하고, 계속 더해주면 된다.
(사실 이걸 못해서 애먹었음)

그리고,
예외처리하기 귀찮으므로 그냥 배열을 1개 더 선언하고
어차피 0으로 초기화되었으므로 걍 인덱스를 1부터 때려박는다.
이렇게 하는게 효율이 나옴 ! ㅠㅠ

2차원 배열 ways를 선언하고
1. 물에 잠긴 곳들을 -1으로 표시한다.
2. m x n만큼 루프를 돌면서
위 or 왼쪽의 값이 -1이 아니면 그 값을, -1이면 0을 더해준다.

알고리즘을 좀 더 공부해야겠다는 생각 !!

#include <string>
#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

int ways[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    for(auto& p : puddles) {
        ways[p[0]][p[1]] = -1;
    }
    
    for (int i = 1 ; i < m + 1 ; i++) {
        for (int j = 1 ; j < n +1 ; j++) {
            if (i == 1 && j == 1) ways[i][j] = 1;
            else if (ways[i][j] != -1) {
                int sum = 0;
                sum += ways[i-1][j] == -1 ? 0 : ways[i-1][j];
                sum += ways[i][j-1] == -1 ? 0 : ways[i][j-1];
                ways[i][j] = sum % 1000000007;
            }
        }
    }
    answer = ways[m][n];
    return answer;
}