Programmers - 등굣길

---

title: Programmers - 등굣길
date: 2022-08-01
tags:

• Algorithm
• DP

---

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

문제 요약

(1,1)에서 (n,m)까지 우측 혹은 하단으로만 이동하여 도착하고자 한다.
중간에 이동하지 못하는 위치가 주어질 때, (n,m)까지 도착할 수 있는 경로의 수를 return한다.

문제 풀이

매우 간단한 DP 문제이나, 말도 안 되는 이유로 Level 3인 것으로 추측하고 있다.


(1,1)에서 우측 및 하단으로 계속 경우의 수를 더해나가면 된다.
다만 물 웅덩이 위치가 주어지므로, 미리 이 위치를 기록하여 해당 위치는 참조하지 않도록 처리한다.


이 문제가 Level 3인 이유는 단 하나이다.
row - column 순서로 데이터가 주어지나, 이 문제는 column - row 순서로 데이터가 주어졌다.
일반적으로 전자를 사용하며, 문제의 모호함을 없애기 위해 순서를 명시한다.
이 문제에서는 후자를 채용하였으며, 순서를 명시하지 않았다.
덕분에 많은 유저들이 전자의 방식으로 풀었다가 틀린 후, 이 부분을 늦게서야 확인하였다.

프로그램

#include <vector>

using std :: vector ;

int solution ( int m , int n , vector < vector < int > > puddles )
{
    int answer = 0 ;
    int iPuddleSize = puddles.size () ;
    vector < vector < int > > vDP ( n , ( vector < int > ( m , 0 ) ) ) ;



    vDP [ 0 ] [ 0 ] = 1 ;
    for ( int i = 0 ; i < iPuddleSize ; ++i )
    {
        vDP [ puddles [ i ] [ 1 ] - 1 ] [ puddles [ i ] [ 0 ] - 1 ] = -1 ;
    }

    for ( int i = 0 ; i < n ; ++i )
    {
        for ( int j = 0 ; j < m ; ++j )
        {
            if ( -1 == vDP [ i ] [ j ] )    // If puddle, ignore
                continue ;

            for ( int k = 0 ; k < 2 ; ++k )
            {
                int iX = i + 1 - k ;        // DOWN , RIGHT
                int iY = j + k ;

                if ( ( n == iX ) || ( m == iY ) || ( -1 == vDP [ iX ] [ iY ] ) )
                    continue ;

                vDP [ iX ] [ iY ] += vDP [ i ] [ j ] ;
                vDP [ iX ] [ iY ] %= 1000000007 ;
            }
        }
    }


    return vDP [ n - 1 ] [ m - 1 ] ;
}