[프로그래머스]2017 카카오코드 예선 : 보행자 천국 (level 3)(c++)

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

코딩테스트 연습 - 보행자 천국

 

DP

#include <vector>

using namespace std;

int MOD = 20170805;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    
    struct from{
        int to_right, to_down;
    };
    
    vector<vector<from>> way_map(m + 1, vector<from>(n + 1));
    way_map[0][1].to_down = 1;
    
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j) 
        {
            // 현재위치가 통행 금지일 때
            if (city_map[i - 1][j - 1] == 1)
            {
                continue;
            }

            /*
                현재 위치값 = left 값 + up 값  (= 이전 위치 값들의 합)

                현재 위치 to_down = left.to_right + left.to_down
                현재 위치 to_right = left.to_right + left.to_down
            */
            from &up = way_map[i - 1][j];
            from &left = way_map[i][j - 1];
            
            int from_up = up.to_right + up.to_down;
            int from_left = left.to_right + left.to_down;
            
            /*
                이전 위치 (left / up)가 좌,우회전 금지일 때
                같은 방향의 값만 가져옴
            */
            if (i - 2 >= 0 && j - 1 >= 0 && city_map[i - 2][j - 1] == 2)
            {
                from_up = up.to_down;
            }
            if (i - 1 >= 0 && j - 2 >= 0 && city_map[i - 1][j - 2] == 2)
            {
                from_left = left.to_right;
            }


            way_map[i][j].to_right = from_left % MOD;
            way_map[i][j].to_down = from_up % MOD;
        }
    }

    // 도착점 값의 합계 반환
    return (way_map[m][n].to_right + way_map[m][n].to_down) % MOD;
}

 

 

2차원 배열에서 시작점 ~ 도착점으로 이동하는 방법의 수 구하기 문제이다.

이 문제의 경우, 어떤 지점은 진행하던 방향만 허용된다는 제약이 있다.

 

city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.

- 0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
- 1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
- 2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다.
(왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)

 

DP로 방향을 잡는다면 문제풀이는 어렵지 않다.

방향에 대한 제약이 있으므로, 메모이제이션을 세로/가로 방향으로 나누어서 해줘야 한다.

기본적인 로직은 다음과 같다.

 

현재 위치로 오는 방향을 나누어 저장하는 것이다.

 

 

 

 

다음은 문제에서 주어진 예시인데, 이 예시로 값 도출과정을 표로 설명해보겠다.

 

 

회색은 통행금지, 주황색은 직진만 해야하는 지점이다. 

 

주어진 배열보다 가로세로가 1씩 큰 배열 W를 만든다.

W의 각 요소에서 right는 가로방향, down은 세로 방향으로 가는 방법의 가짓수를 저장한다.

(나는 가장 첫 번째 요소의 값의 합이 1이 되게끔 하기 위해서 

주어진 크기보다 1씩 여유를 둔 크기로 선언했는데 이는 구현에 따라 다르게 할 수 있다.)

 

<현재> 위치가 직진 통행일 때에는 별다른 제약이 없다. 

왼쪽 위치의 총합 --> 현재 위치의 right.

위쪽 위치의 총합 --> 현재 위치의 down.

이렇게 차곡차곡 저장해나가면 된다.

 

<이전> 위치가 직진 통행일 때를 주의해야 한다.

이전 위치의 방향과 현재 위치의 방향이 일치하는 값만 가져와야 한다. 

예를 들어 위쪽 위치가 직진 통행이라면,

위쪽 위치의 down만 현재 위치의 down으로 가져와야 한다.

 

마찬가지로 왼쪽 위치가 직진 통행이라면,

왼쪽 위치의 right만 현재 위치의 right으로 가져와야 한다.

 

이전 위치가 통행금지라면 당연하게도 가져올 수 있는 값이 없다. 

 

 

 

이렇게 계속 도착점까지 값을 증가시켜 나가면 된다!

마지막에 반환하는 값은 도착점의 right, down값을 합산한 값이다.