[프로그래머스] 등굣길 (C++)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42898?language=cpp# 

코딩테스트 연습 - 등굣길

1. 주의할 점

- 1열과 1행 전부가 도달 가능하지 않을 수 있다

- 연산 이후 값을 저장할 때 MOD를 활용한다

 

2. 구현

- Arr[M][N] 배열에 (M,N)까지 도착 가능한 방법의 수를 MOD로 나눈 값을 저장한다

- Set을 이용하여 웅덩이의 위치를 저장한다

- [1,1]에 시작하여 1열과 1행에 1을 할당해준다. 단, 진행하면서 웅덩이를 만난 경우 해당 방향으로 더 이상 1을 할당하지 않는다

- 2중 For문을 통해 해당 위치까지 도달가능한 방법의 수를 갱신한다(Arr[][])

#define MAX 1000
#define MOD 1000000007
#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
int arr[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    set<int> s;
    for(int i=0;i<puddles.size();i++){
        int val = puddles[i][0]+puddles[i][1]*MAX;
        s.insert(val);
    }
    for(int i=1;i<=m;i++){
        int val = MAX+i;
        if(s.find(val)!=s.end()) break;      //웅덩이
        arr[1][i]=1;
    }
    for(int j=1;j<=n;j++){
        int val = j*MAX+1;
        if(s.find(val)!=s.end()) break;      //웅덩이
        arr[j][1]=1;
    }
    
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            int val = i*MAX+j;
            if(s.find(val)!=s.end()) continue;      //웅덩이
            arr[i][j] = (arr[i-1][j]+arr[i][j-1])%MOD;
        }
    }
    return arr[n][m];
}