[프로그래머스][2017 카카오코드 예선][C++] 보행자 천국

문제

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

코딩테스트 연습 - 리틀 프렌즈 사천성

 

---

문제 풀이

접근 방식

출발점에서 도착점까지 이동 가능한 전체 경로의 수를 구하는 문제이다.

이 문제는 단순한 맵이 아닌 조건이 있는 맵이기 때문에 이를 고려하여 DP 방식으로 문제를 해결해주었다.

 

우선, map의 값이 0인 경우에는 모든 방향으로 움직일 수 있고,

1인 경우에는 갈 수 없으며, 2인 경우에는 직진만 가능하다.

2인 경우에 직진만 가능하기 때문에 수직 방향(↓)과 수평 방향(→)을 나눠서 고려해주어야 한다.

그래서 이중 for문을 돌며 V 벡터에는 수직 방향으로 갈 수 있는 경우의 수를 저장해주었고,

H 벡터에는 수평 방향으로 갈 수 있는 경우의 수를 저장해주어 최종적인 답을 구하였다.

 

---

풀이 코드 - C++

#include <vector>
using namespace std;

int MOD = 20170805;

int solution(int m, int n, vector<vector<int>> city_map) {
    vector<vector<int>> V(m+1, vector<int>(n+1));   // 아래로 이동 가능 횟수
    vector<vector<int>> H(m+1, vector<int>(n+1));   // 오른쪽으로 이동 가능 횟수
    V[1][1] = 1, H[1][1] = 1;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(city_map[i-1][j-1] == 0){
                V[i][j] = (V[i][j] + V[i-1][j] + H[i][j-1]) % MOD;
                H[i][j] = (H[i][j] + V[i-1][j] + H[i][j-1]) % MOD;
            } else if(city_map[i-1][j-1] == 1){
                V[i][j] = 0;
                H[i][j] = 0;
            } else{
                V[i][j] = V[i-1][j];
                H[i][j] = H[i][j-1];
            }
        }
    }
    return H[m][n];
}

실행 결과

실행 결과 : 100.0 (23.38ms)