프로그래머스 - 등굣길 [C/C++]

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

코딩테스트 연습 - 등굣길

코드

#include <string>
#include <vector>
 
using namespace std;
int M, N;
long long dp[101][101];
int map[101][101];
int dy[2] = {0, 1};
int dx[2] = {1, 0};
long long dfs (int y, int x) {
    if (y == M and x == N) return 1;
    if (dp[y][x]) return dp[y][x];
    for (int i = 0; i < 2; i++) {
        if (y > M or x > N or map[y + dy[i]][x + dx[i]]) continue;
        dp[y][x] += dfs(y + dy[i], x + dx[i]) % 1000000007;
    }
    return dp[y][x] % 1000000007;
}
int solution(int m, int n, vector<vector<int>> puddles) {
    M = m, N = n;
    for (auto& iter: puddles) map[iter[0]][iter[1]] = 1;
    return dfs(1, 1) % 1000000007;
}

풀이

출처: 프로그래머스

1. 2차원 평면에서 출발지와 목적지가 주어지면 BFS 혹은 DFS로 풀 수 있습니다.

2. Puddles를 2차원 배열로 받아 갈 수 없도록 표시하여 줍니다

 

3. 시간복잡도가 매우 크기 때문에 다이나믹 프로그래밍을 사용하여, 시간 복잡도를 줄여줍니다.

 

4. 문제에서 요구하는 대로 % 1000000007을 해 줍니다.