(C++) - 프로그래머스(2017 카카오코드 예선) : 보행자 천국

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

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

dp문제였습니다.

 

풀이방법

 1. 0,0에서 출발해서 현재좌표 (i, j)에 따라 다음 행선지를 정합니다.

 

 2. 현재 표지판이 0이라면 우측 또는 아래로 갈 수 있습니다. 현재 표지판이 1이라면 더 이상 갈 수 없으므로 0을 반환합니다. 현재 표지판이 2고 이전 방향이 오른쪽(dir == 1)이라면 오른쪽으로만 갈 수 있고 아래쪽이라면(dir == 2) 아래로만 갈 수 있습니다. 

 

Code

#include <bits/stdc++.h>
using namespace std;
const int MOD = 20170805;
vector<vector<int>> city;
int dist[501][501][3], M, N;

int dp(int m, int n, int dir){
    if(m == M - 1 && n == N - 1) return 1;
    if(m >= M || n >= N || city[m][n] == 1) return 0;
    int &ret = dist[m][n][dir];

    if(ret != -1) return ret;
    ret = 0;
    if(city[m][n] == 0){
        ret = (dp(m,n + 1, 1) + dp(m + 1,n,2)) % MOD;
    }
    if(city[m][n] == 2){
        if(dir == 1) ret = dp(m, n + 1, 1);
        if(dir == 2) ret = dp(m + 1, n, 2);
    }
    return ret % MOD;
}

int solution(int m, int n, vector<vector<int>> city_map) {
    city = city_map;
    M = m, N = n;
    memset(dist,-1,sizeof(dist));
    return dp(0,0,0);
}