Programmers_Level3_등굣길

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

프로그래머스

 

---

 

 

깊이 탐색으로 학교에 도착하는 길의 갯수를 세다보니 효율성 테스트에서 걸렸다. 

최단거리의 경우의 수를 찾는 다른 접근이 필요했다.

 

왼쪽 위에서 오른쪽 아래로 가야하고 오른쪽과 아래 이동밖에 없으니 

짧은 길을 비교할 필요 없이 출발부터 도착까지의 경우의 수만 찾으면 된다. 

 

집[1,1]부터 [1,2]로 가는 길은 하나 밖에 없다. 

또 집[1.1]부터 [2.1]으로 가는 길 또한 하나 밖에 없다. 

[1,1]에서 [2,2]로 가는 경우의 수는 2가지이다. 

[1,2]에서 아래로 내려가는 것과 [2.1]에서 오른쪽으로 가는 것이다. 

 

[3,2]의 경우의 수를 보면 [1,3]에서 아래로 내려가는 것과 

[2,2]에서 오른쪽으로 가는 것 두가지 밖에 없다. 

[2.2]로 가는 길은 2가지이니 [3,2]로 가는 길은 3가지가 나온다. 

 

보다보면 띠-링하고 보인다. 

[x,y] 의 경우의 수는 [x-1][y]의 경우의 수와 [x][y-1]의 경우의 수의 합과 같다. 

이걸 해결한 방법은 다음과 같다. 

빈 2차원 백터에 웅덩이의 좌표를 -1으로 해두었다.

웅덩이를 0으로 두면 아직 확인하지 않은 곳과 웅덩이를 구분할 수가 없다. 

 

맨 첫 행과 첫 열은 경우의 수가 1이으로 처음엔 1을 넣었다가 

[1.2]와 [2.1] 또한 웅덩이가 될 수 있기 때문에 첫 행은 자신의 왼쪽의 값으로 

첫 열은 자신의 윗쪽의 값으로 설정한다. 

 

[3,2]가 웅덩이인 경우

 

-1인 웅덩이를 만나면 0으로 바꾸고 앞서서 찾았던 점화식을 이용하면 끝이다. 

 

구현 코드

#include <iostream> 
#include <vector> 

using namespace std; 

class findWay
{
    private: 
    vector<vector<int>> map;
    vector<vector<int>> puddles;
    int m, n;

    public:
    findWay(int m, int n, vector<vector<int>> puddles)
    {
        this->m = m;
        this->n = n;
        map.assign(n, vector<int>(m, 0));
        this->puddles = puddles;
        for(auto& vec : puddles)
        {
            map[vec[1]-1][vec[0]-1] = -1;
        }
    }

    int findShortestWays();
};

int findWay::findShortestWays()
{    
    for(int y = 0; y < n; ++y)
    {
        for(int x = 0; x < m; ++x)
        {
            // 웅덩이
            if(map[y][x] == -1)
            {
                map[y][x] = 0;
            }
            else if( y == 0 && x == 0)
            {
                map[y][x] = 1;
            }
            // 첫 행
            else if(y == 0)
            {
                map[y][x] = map[y][x-1];
            }
            // 첫 열
            else if(x == 0)
            {
                map[y][x] = map[y-1][x];
            }
            else
            {
                map[y][x] = (map[y-1][x] + map[y][x-1]) % 1000000007 ;
            }
        }
    }
    return map[n-1][m-1];
}

int solution(int m, int n, vector<vector<int>> puddles) {
    findWay myWay(m, n, puddles);
    return myWay.findShortestWays();
}