프로그래머스 문제 - 보행자 천국

프로그래머스 보행자 천국 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

교차로마다 임의의 표지판이 설치된 도로가 주어집니다.
자동차는 오른쪽이나 또는 아래로만 이동이 가능합니다.
0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)
위와 같은 표지판들이 설치된 도로가 주어질 때 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력해야 합니다.
가능한 경로 수가 많으므로 20170805로 나눈 나머지 값을 출력해야 합니다.

문제 풀이

길의 모든 경로 수를 찾는 문제입니다.
거기에 추가적으로 길을 막는 상황이나 회전하지 못하는 상황까지 추가되었습니다.

최단 거리인 전체 경로 수를 찾는 방법은 2차원 배열로 이동 가능한 값들을 저장하고 더하며 답을 찾아낼 수 있습니다.
예로 들면
0, 0, 0, 0
0, 0, 0, 0
0, 0, 0, 0
0, 0, 0, 0
이런 식의 도로가 주어진다면
1, 1, 1, 1
1, 2, 3, 4
1, 3, 6, 10
1, 4, 10, 20
이런식으로 dp[i][j] = dp[i-1][j] + dp[i][j-1]식을 이용하여 답을 찾아낼 수 있습니다.

이번 문제도 똑같은 식을 사용하여 문제를 풀되 회전하지 못하는 상황을 고려해야 합니다.
dp[i-1][j]의 교차로가 만약 2라고 생각했을 때 dp[i-1][j]의 교차로에 도착한 차량 중 오른쪽으로 이동하던 차량만 dp[i][j] 교차로에 올 수 있게 됩니다.
그리고 dp[i][j-1]의 교차로가 만약 2라고 생각했을 때도 마찬가지로 dp[i][j-1]의 교차로에 도착한 차량 중 아래로 이동하던 차량만 dp[i][j] 교차로에 올 수 있게 됩니다.

이를 알아내기 위해 전에 이동했던 방향 두가지인 오른쪽, 아래를 추가로 저장 및 고려하며 dp값을 구해나가면 됩니다.

또한 모든 값은 20170805로 나눈 나머지 값이 나와야 하기 때문에 수시로 값을 나눠주어야 합니다.

전체 코드

#include <bits/stdc++.h>
#include <vector>

using namespace std;

int MOD = 20170805;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    //first : 오른쪽으로 오던 자동차, second : 아래로 오던 자동차
    vector<vector<pair<int, int>>> dp(500, vector<pair<int, int>>(500, make_pair(0, 0)));
    
    dp[0][0] = make_pair(1, 1);
    //0번째 줄에 값 넣어줌
    for(int i = 1; i < n; i++)
    {
        if(city_map[0][i] != 1)
        {
            dp[0][i].first = dp[0][i-1].first;
        }else
        {
            break;
        }
    }
    
    for(int i = 1; i < m; i++)
    {
        if(city_map[i][0] != 1)
        {
            dp[i][0].second = dp[i-1][0].second;
        }else
        {
            break;
        }
    }
    
    for(int i = 1; i < m; i++)
    {
        for(int j = 1; j < n; j++)
        {
            //벽일 경우 이동 가능한 수는 없음
            if(city_map[i][j] == 1)
            {
                dp[i][j] = make_pair(0, 0);
                continue;
            }
            
            //전에 움직였던 방향이랑 같은 방향으로 움직일 경우에는 1만 아니면 무조건 이동 가능
            //0이라면 모두 더해줌
            dp[i][j].second = (dp[i-1][j].second) % MOD;
            if(city_map[i-1][j] == 0)
            {
                dp[i][j].second += (dp[i-1][j].first) % MOD;
            }
            
  
            dp[i][j].first = (dp[i][j-1].first) % MOD;
            if(city_map[i][j-1] == 0)
            {
                dp[i][j].first += (dp[i][j-1].second) % MOD;
            }
            
        }
    }
    
    answer = (dp[m-1][n-1].first + dp[m-1][n-1].second) % MOD;
    
    return answer;
}

출저

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