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

탐욕알고리즘 (Greedy)

n*m 그리드에서 1,1부터 n,m까지 가는 최단 경로의 경우의 수를 1000000007 로 나눈 나머지를 반환하는 문제

가는 경로에 침수된 지점이 k 개 주어진다 (좌표로 주어짐)

 

접근방법

n*m만큼의 2차원 배열 map을 만들고, 0으로 초기화한 후, 침수된 지점은 -1로 표시한다.

1,1부터 n,m까지 순회하면서 각 자리에 이 지점까지 오는 경우의 수를 저장한다.

즉, r,c 지점은 한칸 왼쪽 자리까지 오는 경우 + 한칸 위쪽 자리까지 오는 경우, 이 두 경우의 수를 합한 경우다.

1,1자리에 처음에 1을 넣고 차례로 순회하고나면 n,m에는 학교까지 오는 데 최단거리의 경우의 수가 담긴다.

(최단거리인지 체크하지 않는 이유는, n과 m이 1보다 크거나 같고, 오른쪽과 아래쪽으로 밖에 이동하지 못하기 때문에 이렇게만 이동하면 어떻게 가도 최단거리)

단, 순회하면서 침수당한 지점의 값은 갱신하지 않고, 만약 내 왼쪽이나 내 위쪽이 침수당한 지점이라면 그 값은 더하지 않는다.

그리고 1000000007 로 나눈 나머지를 출력하는 문제이므로 더할 때에도 1000000007 를 나눈 값을 더해준다.

 

오답노트

침수당한 곳 표시할 때 m,n바꿔써서 틀렸었음..;

 

소스코드

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

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    vector<vector<int>> map(n+1, vector<int>(m+1, 0));
    for(vector<int> puddle : puddles){
        map[puddle[1]][puddle[0]] = -1;
    }
    
    map[1][1] = 1;
    
    for(int r = 1 ; r <= n ; r++){
        for(int c = 1 ; c <= m ; c++){
            if(map[r][c] != -1){
                if(map[r][c-1] != -1){
                    map[r][c] += (map[r][c-1] % 1000000007);
                }
                if(map[r-1][c] != -1){
                    map[r][c] += (map[r-1][c] % 1000000007);
                }
            }
        }
    }
    
    return map[n][m] % 1000000007;
}

 

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

프로그래머스