Programmers - 보행자 천국

---

title: Programmers - 보행자 천국
date: 2022-07-26
tags:

• Algorithm
• DP

---

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

문제 요약

2차원 지도와 도로의 상태가 주어진다. 0이면 제한 X, 1이면 금지, 2라면 동일한 방향으로만 진행할 수 있다.
(0,0) 위치에서 (m-1,n-1) 위치까지 이동하는 경로 % 20172805를 return한다.

문제 풀이

도로의 상태가 없는 2차원 지도에서 경우의 수를 구하는 문제의 발전형이다.
통행 금지의 경우 값을 갱신하지 않으면 되지만, 동일한 방향으로만 진행하는 조건이 있다. 이는 이동하는 방향을 나누어 처리해주어야 한다는 뜻이다.
2차원 DP를 베이스로 하되, 방향을 처리해주어야 하므로 추가적인 2개의 항을 추가한 3차원 DP를 이용한다.


[ i ] [ j ] [ n ] 은 ( i , j ) 위치에서 각 방향으로 갈 수 있는 경우의 수이다. 도착 위치의 도로 상태에 따라 처리를 나누어준다. 1이라면 통행 금지이므로 처리하지 않는다. 처음에 0으로 초기화 하였기에 문제가 없다. 이후 두 가지 방향에 맞게 처리해준다. 좌측에서 현재 위치로 이동은 우측 진행이므로, 이 값을 현재 위치에서 우측 이동으로 그대로 집어넣는다. 그리고 현재 도로의 상태가 2라면 그대로 끝내고, 0이라면 하단으로도 이동할 수 있도록 더해준다. 마지막( m - 1 , n - 1 )위치의 값은( 좌측에서 우측으로 진행하는 경우의 수 + 상단에서 하단으로 진행하는 경우의 수 ) % MOD 이다.


현재 문제는 사각형 격자에서 진행 가능한 경로의 수를 계산한다.
실제 도로에서는 훨씬 많은 도로가 존재한다. 지하도로, 고가, 회전교차로, 90도가 아닌 3개 혹은 5개 이상의 도로 등 많은 도로가 존재한다.
이는 네비게이션에서 이용할 수 있다. 시작점과 도착점을 받아온 후, 경우의 수를 계산하고 예상 소요 시간 및 운행 거리 등을 보내줘야 한다.
도로의 수가 매우 많기에 LinkedList와 유사하지만, 많은 방향을 가질 수 있는 자료구조를 만들어서 사용할 것 같다.
직진이 아닌 회전을 조금이라도 할 경우 노드를 생성하며, 노드간의 거리와 예상 소요 시간을 저장한다.
그럼에도 너무 많은 연산이 일어나므로 주로 이용하는 도로 혹은 일정 거리 간격으로 운행 정보를 미리 계산할 수도 있을 것이다.
이러한 작업을 통해 요청이 들어왔을 때 연산해야 하는 데이터의 양을 적게 하여 운행 정보를 다시 보내기까지 소요되는 시간을 줄일 수 있을 것이다.

프로그램

#include <vector>

using std :: vector ;

int MOD = 20170805;

int solution ( int m , int n , vector < vector < int > > city_map )
{
    int answer = 0 ;
    vector < vector < vector < int > > > vDP ( m , ( vector < vector < int > > ( n , ( vector < int > ( 2 , 0 ) ) ) ) ) ;         // [ X ] [ Y ] [ 0 : Vertical, 1 : Horizontal]



    vDP [ 0 ] [ 0 ] [ 0 ] = vDP [ 0 ] [ 0 ] [ 1 ] = 1 ;

    for ( int i = 0 ; i < m ; ++i )
    {
        int * ipMap = city_map [ i ].data () ;

        for ( int j = 0 ; j < n ; ++j )
        {
            int iMapIndicator = * ipMap ++ ;
            int irgXDirection [ 2 ] = { 0 , -1 } ;
            int irgYDirection [ 2 ] = { -1 , 0 } ;

            if ( 1 == iMapIndicator )            // Forbidden
                continue ;

            for ( int iDirection = 0 ; iDirection < 2 ; ++ iDirection )             // 0 : Count left, 1 : Count up
            {
                int iTempX = i + irgXDirection [ iDirection ] ;
                int iTempY = j + irgYDirection [ iDirection ] ;


                if ( ( iTempX < 0 ) || ( m - 1 < iTempX ) || ( iTempY < 0 ) || ( n - 1 < iTempY ) )         // Out of bound
                    continue ;


                vDP [ i ] [ j ] [ iDirection ] += vDP [ iTempX ] [ iTempY ] [ iDirection ] ;
                vDP [ i ] [ j ] [ iDirection ] %= MOD ;

                if ( 0 == iMapIndicator )
                {
                    vDP [ i ] [ j ] [ ( iDirection + 1 ) & 1 ] += vDP [ iTempX ] [ iTempY ] [ iDirection ] ;
                    vDP [ i ] [ j ] [ ( iDirection + 1 ) & 1 ] %= MOD ;
                }
            }
        }
    }


    return ( vDP [ m - 1 ] [ n - 2 ] [ 0 ] + vDP [ m - 2 ] [ n - 1 ] [ 1 ] ) % MOD ;
}