[프로그래머스] 보행자 천국 c++

[프로그래머스] 보행자 천국 c++

문제 링크 : 프로그래머스 보행자 천국

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

 

문제 설명

카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.

도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.

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

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

도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라. 이때 가능한 경로의 수는 컴퓨터가 표현할 수 있는 정수의 범위를 넘어설 수 있으므로, 가능한 경로 수를 20170805로 나눈 나머지 값을 출력하라.

 

입력 형식

입력은 도시의 크기를 나타내는 m과 n, 그리고 지도를 나타내는 2차원 배열 city_map으로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 500
• city_map의 크기는 m × n이다.
• 배열의 모든 원소의 값은 0, 1, 2 중 하나이다.
• 출발점의 좌표는 (0, 0), 도착점의 좌표는 (m - 1, n - 1)이다.
• 출발점과 도착점의 city_map[i][j] 값은 0이다.

출력 형식

출발점에서 도착점까지 이동 가능한 전체 경로의 수를 20170805로 나눈 나머지를 리턴한다.

예제 입출력

m	n	city_map	answer
3	3	[[0, 0, 0], [0, 0, 0], [0, 0, 0]]	6
3	6	[[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]]	2

예제에 대한 설명

첫 번째 예제는 모든 도로가 제한 없이 통행 가능한 경우로, 가능한 경우의 수는 6가지이다.
두 번째 예제는 문제 설명에 있는 그림의 경우이다. 가능한 경우의 수는 빨간 실선과 노란 점선 2가지뿐이다.

 

---

풀이 과정

일단 나는 문제를 제대로 안읽는다는 것을 깨달았다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다 라는 조건을 생략해버리고 4가지 경로를 다 생각했었고, 각 벡터의 사이즈를 제대로 확인하지 않아서 BFS로 접근을 했다. 푸는데 하도 답이 제대로 안맞아 떨어져서 다시 보니까 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다 라는 조건이 있었다.

보통, DP 문제 같은 경우에는 위 조건을 통해서 점화식을 유추할 수 있게끔 문제가 나오는데 각 m, n의 사이즈를 보지 않았어도 이 부분만 봤다면 바로 DP로 접근했을텐데..... 아, 시간 날렸다.... 어쨋든, 문제에 집중해보자면....

DP로 접근했을 때는 다음과 같이 3차원 배열로 풀어낼 수 있을 것 같다. 즉, dp[y][x][왔던방향] 식으로 선언해서 풀 수 있을 것 같다.

 

1. 먼저 DP에서 가장 중요한 요소는 초기화다. 즉, 인덱스 상으로 1번째까지는 답을 알 수 있으니 초기화를 시켜준다 -> 첫번째 행과 열들에 대해 초기화 시켜준다.
2. 그 뒤로는 2중 반복문을 돌면서 이전 값에서 어떻게 다음 값을 유추할 수 있는지에 대한 점화식을 세운다.
3. 즉, 주석에 작성한 것처럼, 바로 위 칸이 0(프리한 길)이면, 현재 위치의 위에서 온 길의 수 += (위쪽칸에서 왼쪽으로 온 길의 수 + 위쪽칸에서 위쪽으로부터 쭉 온 길의 수) 처럼 경우에 맞춰서 점화식을 작성한다.
4. 마지막 답을 어떤 수를 나눠야 하는 경우, 나는 주로 최종 로직에서 나머지 연산을 한다. 허나 이렇게 풀면 답이 틀리게 나올 때가 많다. 그러므로, 연산이 끝날 때마다 해당 로직(어떤 수로 나눠야 하는)을 처리해주자.

 

코드

#include <string>
#include <vector>

using namespace std;

int MOD = 20170805;

int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    // 마지막 차원은 왼쪽에서 왔는지, 위에서 왔는지 => 왼쪽=0, 1=위쪽
    vector<vector<vector<long long>>> dp(m+1, vector<vector<long long>>(n+1, vector<long long> (2)));

    // 0: 프리한 길
    // 1: 통행 금지
    // 2: 왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만

    // 초기화
    for(int i = 0; i < m; i++) {
        if(city_map[i][0] == 1)
            break;
        dp[i][0][1] = 1;
    }

    for(int i = 0; i < n; i++) {
        if(city_map[0][i] == 1)
            break;
        dp[0][i][0] = 1;
    }

    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            // 바로 위 칸이 프리한 길이면
            if(city_map[i-1][j] == 0) {
                // 위에서 온 길의 수 += (위쪽칸에서 왼쪽으로 온 길의 수 + 위쪽칸에서 위쪽으로부터 온 길의 수)
                dp[i][j][1] += (dp[i-1][j][0] + dp[i-1][j][1]) % MOD;
            }
            // 바로 위 칸이 좌회전 우회전 금지 길이면
            if(city_map[i-1][j] == 2) {
                // 위에서 온 길의 수 += 위쪽칸에서 위쪽으로부터 온 길의 수
                dp[i][j][1] += (dp[i-1][j][1] % MOD);
            }
            // 바로 왼쪽칸이 프리한 길이면
            if(city_map[i][j-1] == 0) {
                // 왼쪽에서 온 길의 수 += 왼쪽칸에서 왼쪽으로부터 온 길의 수 + 윈쪽칸에서 위쪽으로부터 온 길의 수)
                dp[i][j][0] += (dp[i][j-1][0] + dp[i][j-1][1]) % MOD;
            }
            // 바로 왼쪽칸이 좌회전 우회전 금지 길이면
            if(city_map[i][j-1] == 2) {
                // 왼쪽에서 온 길의 수 += 왼쪽칸에서 윈쪽으로부터 온 길의 수
                dp[i][j][0] += (dp[i][j-1][0] % MOD);
            }
        }
    }

    answer = (dp[m-1][n-1][0] + dp[m-1][n-1][1]) % MOD;

    return answer;
}