[프로그래머스] 등굣길

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector<vector<int>> road(n, vector<int>(m, 0));
    
    road[0][0] = 1;
    
    for(const auto& puddle : puddles) {
        road[puddle[1] - 1][puddle[0] - 1] = -1;
    }
    
    for(int r=0; r<n; r++){
        for(int c=0; c<m; c++){
            if(road[r][c] == -1){
                road[r][c] = 0;
                continue;
            }
            
            if(r > 0) {
                road[r][c] = (road[r][c] + road[r-1][c]) % 1000000007;
            }
            
            if(c > 0) {
                road[r][c] = (road[r][c] + road[r][c-1]) % 1000000007;
            }
        }
    }
    
    return road[n-1][m-1];
}

---

📝 풀이

⭐ 주의 : 이 문제는 행과 열이 반대로 주어집니다.

시작 위치를 1로 초기화 한 후 물 웅덩이 위치를 -1로 표시합니다.

물 웅덩이를 만나면 경로가 없으므로 0으로 초기화 합니다.

물 웅덩이가 아니라면 위의 길과 왼쪽 길의 값을 더합니다.

위의 길이나 왼쪽 길은 없을 수도 있으므로 있는 경우만 더합니다.

최종적으로 학교의 위치에 경로의 수가 저장됩니다.

따라서 road[n-1][m-1] 값을 return 합니다.