[프로그래머스 :: DP] 등굣길

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

코딩테스트 연습 - 등굣길

 먼저 떠오른 방법은 DFS, 정확성 테스트를 통과하였으나 효율성 테스트를 통과하지 못했다. 2차원 백터 위에서 동적할당 기법을 사용하면 된다는 생각은 했는데, 최단 거리 조건을 어떻게 넣을지 몰라 헤매다가 다른 풀이를 찾아보았다.

 

 그런데 최단 거리 조건은 고려할 필요가 없었다. 왔던 자리를 돌아가지 않으면 최단거리 조건을 만족하기 때문이다. DP 기법을 사용할 때 최단 거리 문제는 이미 해결 된 것이다. 이제 아래쪽, 오른쪽으로만 움직일 수 있는 조건만 고려해주면 된다.

 2차원 백터를 순서대로 순회하면서 왼쪽와 위쪽의 경우를 합해주면 된다.

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

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
	// 첫 번째 백터와 두 번째 백터는 y값의 차이이므로 n을 넣어준다.
    // 첫 번째 백터의 첫째값과 둘째값은 x값의 차이이므로 m을 넣어준다. 
    vector<vector<int>> dim2(n+1,vector<int>(m+1,0));

	// 2차원 백터에 좌표를 할당할 때 헷갈리면 Out of Bound Error가 나타난다.
    for(int i=0; i<puddles.size(); ++i){
        int y = puddles[i].at(1);
        int x = puddles[i].at(0);
        dim2.at(y).at(x) = -1;
    }

	dim2.at(1).at(1) = 1;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            if(dim2.at(i).at(j)==-1) continue;
            if(dim2.at(i-1).at(j)!=-1) dim2[i][j] += dim2[i-1][j];
            if(dim2.at(i).at(j-1)!=-1) dim2[i][j] += dim2[i][j-1];
            dim2[i][j] %= 1000000007;
        }
    }
    return dim2.at(n).at(m);
}

---

 DP로 어떻게 최단거리를 확인할 수 있는지 아이디어가 떠오르지 않아 DFS를 사용하였다. 효율성 테스트를 통과하지 못한다.

 

정확성 테스트만 통과

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

using namespace std;

int M, N;
int min_Depth;
vector<int> dist;

void dfs(vector<vector<int>> &dim2, int depth, int cur_x, int cur_y){
    if( cur_y>N || cur_x>M){ return; } 
    else if(dim2.at(cur_y).at(cur_x)==-1){ return; }
    else if(dim2.at(cur_y).at(cur_x) < depth){ return; }
    
    if(cur_y==N && cur_x==M){ dist.push_back(depth); }
    dim2.at(cur_y).at(cur_x) = depth;
    dfs(dim2, depth+1, cur_x+1,cur_y);
    dfs(dim2, depth+1, cur_x,cur_y+1);    
}

int solution(int m, int n, vector<vector<int>> puddles) {
    M = m;
    N = n;
    min_Depth = M*N;
    vector<vector<int>> dim2(n+1,vector<int>(m+1,M*N));

    for(int i=0; i<puddles.size(); ++i){
        int y = puddles[i].at(1);
        int x = puddles[i].at(0);
        dim2.at(y).at(x) = -1;
    }
    dfs(dim2,1,1,1);

    int answer = 0;
    for(int i=0; i<dist.size(); ++i)
        dist[i] = dist[i] % 1000000007;
    
    sort(dist.begin(), dist.end());

    for(int i:dist)
        if(i==dist.at(0)){ answer++; }
    
    return answer;
}