[프로그래머스] 등굣길

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
• m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

---

풀이

70분
같은 분류의 Level3 문제를 10분만에 풀고 자신감에 풀었는데 엄청난 시간이 걸려버렸다. 문제 풀이는 빠르게 생각했지만 문제가 있었다. 우선 이런 보드판? 형식의 문제에서 항상 헷갈리게 하는 행 번호/ 열 번호 문제이다. 내가 편한대로 가로/세로를 행/렬로 바꿔 푸는 과정에서 입력값인 puddles의 순서는 그대로 사용해버려서 헤맸다.

// map[v[0] - 1][v[1] - 1] = -1 로 생각했었음
for(vector<int> v : puddles) map[v[1] - 1][v[0] - 1] = -1;

하지만 실수를 고치고도 하나의 테스트 케이스를 통과하지 못 해서 매우 매우 매우 긴 시간을 고민하게 되었다. 해당 테스트 케이스가 100x100 사이즈의 보드판을 사용해서, 결과를 출력해도 문제를 한눈에 알아차릴 수 없었다. 정말 도저히 모르겠어서 일단은 제출을 했는데 통과해버렸다.(!??)
예전에 푼 적이 있는 문제였는데 아마 그 때 내가 추가한 잘못된 테스트 케이스인 것 같다. 그 때는 어떻게 잘못된 테스트 케이스를 써서 통과했는지 의문이 들고, 프로그래머스에서 초기화를 해도 테스트 케이스는 남아있다는 것을 알게되었다.

코드

// 09:00 ~ 10:10
#include <string>
#include <vector>

using namespace std;

int map[100][100];

int solution(int m, int n, vector<vector<int>> puddles) {
    int res = 0;
    for(vector<int> v : puddles) map[v[1] - 1][v[0] - 1] = -1;
    for(int i = 0; i < m; ++i){
        if(map[0][i] == -1) break;
        map[0][i] = 1;
    }
    // map[n][m] n:행, m:열
    for(int i = 1; i < n; ++i){
        for(int j =0; j < m; ++j){
            if(map[i][j] == -1) continue;
            
            if(j == 0) map[i][j]  = map[i-1][j];
            else{
                if(map[i - 1][j] != -1) map[i][j] += map[i - 1][j];
                if(map[i][j - 1] != -1) map[i][j] += map[i][j - 1];
            }
            map[i][j] = map[i][j] % 1000000007;
        }
    }
    
    if(map[n-1][m-2] > 0) res += map[n-1][m-2];
    if(map[n-2][m-1] > 0) res += map[n-2][m-1];
    
    return res % 1000000007;
}