프로그래머스 : 등굣길 c++ (DP 연습)

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

코딩테스트 연습 - 등굣길

 

풀이

일단 최단경로의 갯수이기 때문에 DP로 푸는 방식이 맞다.

 + 사방으로 움직이는거도 아니고, 오른족과, 아래쪽만이라 더더욱 DFS,BFS로 풀 이유가 없다.

 

1. DP이기 때문에 map을 만드는게 아니라, 출발지에서 해당 좌표로 가는 최단거리의 갯수를 저장

 

2. find 함수를 사용할건데, pair를 사용해서 코드를 간략하게 할거라서, puddles 배열을 새로운 vector에 저장

-> 못찾았을때 find 함수는 end() 값을 return 한다

 

3. 오른쪽, 아래쪽 밖에 못가기 때문에 0행, 0열을 모두 직전 값으로

 

4. 본인 윗값 + 왼쪽 값이 해당 좌표로 오는 최단경로 갯수

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    int answers[m][n];
    
    vector<pair<int,int> > puddle;
    
    for(int i=0;i<puddles.size();i++)
    {
        puddle.push_back(make_pair(puddles[i][0]-1,puddles[i][1]-1));
    }
    
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==0 && j==0)
            {
                answers[i][j] = 1;
            }
            else if(find(puddle.begin(),puddle.end(),make_pair(i,j)) != puddle.end())
            {
                answers[i][j] =0;
            }
            else if(i==0)
            {
                answers[i][j] = answers[i][j-1] % 1000000007;
            }
            else if(j==0)
            {
                answers[i][j] = answers[i-1][j] % 1000000007;
            }
            else
            {
                answers[i][j] = (answers[i-1][j]+answers[i][j-1]) % 1000000007;
            }
            
        }
    }
    answer = answers[m-1][n-1];
    return answer;
}