프로그래머스 Level3 - 등굣길 C++

코딩테스트 연습 - 등굣길

#include <string>
#include <vector>
#include <cstring>
#define mod 1000000007
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    // m : 가로, n : 세로, puddles : 물이 담긴 곳
    long long arr[m+1][n+1];
    memset(arr, 0, sizeof(arr));
    // 초기화는 (0,0), (0,1), (1,0) 은 1로 초기화
    arr[1][1] = arr[1][2] = arr[2][1] = 1;
    
    for (int i = 0; i < puddles.size(); i++)
		arr[puddles[i][0]][puddles[i][1]] = -1;
    
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(arr[i][j] == -1)
                arr[i][j] = 0;
            else if (arr[i][j] == 0)
                arr[i][j] = (arr[i][j-1] + arr[i-1][j]) % mod;
        }
    }
    answer = arr[m][n] % mod;
    return answer;
}

---

 마침 고등학교였나 확통에서 길찾기 문제 풀이하는걸 배운게 기억이 났습니다. 자세한 내용은 아래 링크에

[적분과 통계 44탄] 최단거리 길찾기

 처음에 했을땐 값이 무슨 400만, 500만 나와서 당황했는데 memset를 통해 초기화를 하니 값이 잘 나왔습니다.

---

처음에는 vector<vector<int>> 형태가 어떤건지 잘 몰랐는데 위 방식처럼 puddles[i][j] 같은 식으로 꺼내 쓰면 될 것 같습니다. 안쪽 벡터의 경우 [2,2] 처럼 한 벡터만 있으니 0, 1만 사용해도 됩니다.