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

 처음 봤을 때는 응? 이거완전 BFS인데... 라고 생각했으나 일단 (왜인지는 몰라도) 테케 정확도도 통과하지 못했다. 이후에는 문제 분류인 DP로 풀어나갔다. 

그러나 얼추맞는 것 같은데 이상하게 통과가 안되서 알아보니 학교의 위치는 m,n 이었다 ! 

이 때문에 테스트 케이스를 어느정도 통과했으나 아직 예외가 존재했고 예외를 찾는데는 얼마안걸렸지만 구현이 좀 걸렸다. 일단 풀이 방법은 다음과 같다. 

 

1. x, y 에서 x가 0이거나 y가 0이면 모두 DP[x][y] 는 1이다. 최소로 갈 수 있는 값이 1개 밖에 없다.

2. DP[x][y] 는 현재 위치의 왼쪽과 위의 합이다. 왜냐면 집이 왼쪽 위에 있기 때문이다. 여기까지가 기본이다.

3. 1번에서 [0,1],  [0,2] , [0,3] 중 0,2 가 웅덩이라면 갈 수 없다. 그리고 자연스럽게 0,3도 지나갈 수 없다. 갈 일 이 없기 때문이다. 이때는 -1로 정해둔다.

4. 2번에서 왼쪽과 위쪽 둘다 -1 로 웅덩이일수 있다. 이때는 아래에서 들어와야한다. 아래도 웅덩이라면 이 곳 또한 지나갈 일이 없다.

 

2차원 DP를 연습하기 좋은 문제라고 생각한다. DFS + DP 로도 풀 수 있는데 아직까지 DFS DP는 잘 모르겠다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;

long long DP[MAX][MAX];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            DP[i][j] = 0;
            if(i == 0 && j != 0)
                DP[i][j] = 1;
            else if(i != 0 && j == 0)
                DP[i][j] = 1;
        }
    }    
    
    for(int i = 0; i < puddles.size(); i++){
        int x = puddles[i][1];
        int y = puddles[i][0];
        
        if(x - 1 == 0){
            for(int j = y - 1; j < m; j++)
                DP[x - 1][j] = -1;
        }else if(y - 1 == 0){
            for(int j = x - 1; j < n; j++)
                DP[j][y - 1] = -1;
        }else
            DP[x - 1][y - 1] = -1;
    }
    
    for(int i = 1; i < n; i++){
        for(int j = 1; j < m; j++){
            if(DP[i][j] == -1) continue;
            if(DP[i - 1][j] != -1 && DP[i][j - 1] != -1){
                DP[i][j] = DP[i][j - 1] % 1000000007 + DP[i - 1][j] % 1000000007;
            }
            else if(DP[i - 1][j] == -1 && DP[i][j - 1] == -1){
                if(DP[i + 1][j] == -1)
                    DP[i][j] = -1;
                else
                    DP[i][j] = DP[i + 1][j];
            }else{
                DP[i][j] = max(DP[i][j - 1] % 1000000007, DP[i - 1][j] % 1000000007);
            }
        }
    }
    
    
    
    answer = DP[n - 1][m - 1] % 1000000007;
    
    
    if(answer == -1)
        answer = 0;
    return answer;
}