[C/C++] Lv3 프로그래머스 - 보행자 천국

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

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

- 접근법

이산수학에서도 단골로 나오고, 기본적인 DP문제로도 나오는 유형인 최단거리 수 찾기 문제이다.

이 문제는 기본적인 문제에서 조건 하나를 추가해서 살짝 꼰것 같은 문제지만 해결방법은 크게 다르지않다.

 

먼저 이 문제에서 도로의 유형은 0,1,2 로 주어지는데 0은 자유롭게 지나갈 수 있는 길, 1은 벽(못지나감), 2는 오는 방향으로부터 직진만 가능하다. (문제에선 좌회전, 우회전 어렵게 써놨지만 쉽게 생각하면 다음과 같이 풀어쓸 수 있다)

 

이 세가지 유형에서 2를 제외하면, 아주 아주 쉬운 기본적인 DP 문제로 볼 수 있다.

Dy[i][j] = (0,0)에서 (i,j)까지 가는 최단경로의 갯수

Dy[i][j] = (i-1,j)까지 온 최단경로의 갯수 + (i,j-1)까지 온 최단경로의 갯수

즉 Dy[i][j]=Dy[i-1][j]+Dy[i][j-1] 로 표현할 수 있다.

 

그리고 이제 문제에서 주어진 조건, 2를 추가하고 다시 생각해본다면.

도로의 유형이 2 라는 것은, 오는 방향으로부터 직진만 가능한 도로라고 볼 수 있다.

따라서 본래의 점화식 Dy[i][j]=Dy[i-1][j]+Dy[i][j-1] 에서 각각 i-1이 2라면 i-2를 보고 또 2라면 i-3을 보면서 벽(1)이 나타나면 오는 경유해서 오는 경로가 없다는 것이고, 0이 나타난다면 그 위치의 값으로 대체하면 된다.

이 방식을 i-1,j (위쪽) i,j-1 (왼쪽) 각각 해주면 된다.

 

---

- 유사문제

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

똑같은 문제이다. 오히려 이 문제는 0,1,2 중에서 2가 없어져서 0,1만 고려하면 되는 아주 쉬운 문제이다.

만약 보행자 천국을 풀기전에 등굣길 을 안풀었다면 이 문제부터 풀고 푸는것을 추천한다.

(이러한 유형의 문제는 모두 똑같은 점화식으로 풀린다)

 

 

---

- 소스코드

#include <vector>
#include <iostream>
using namespace std;
 
int MOD = 20170805;
int Dy[505][505];
int board[505][505];
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
void init(int m,int n,vector<vector<int> > city_map) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = city_map[i][j];
            Dy[i][j] = 0;
        }
    }
    for(int i=0;i<m;i++) {
        if(city_map[i][0]==0) Dy[i][0]=1;
        if(city_map[i][0]==1) break;
    }
    for(int i=0;i<n;i++) {
        if(city_map[0][i]==0) Dy[0][i]=1;
        if(city_map[0][i]==1) break;
    }
}
int path_calc(int x, int y) {
    int count = 1;
    int sum_A = 0, sum_B = 0, sum = 0;
    while (x - count >= 0) {
        if (board[x - count][y] == 1) break;
        if (board[x - count][y] == 0) {
            sum_A = Dy[x - count][y];
            break;
        }
        count++;
    }
    sum_A %= MOD;
    count = 1;
    while (y - count >= 0) {
        if (board[x][y - count] == 1) break;
        if (board[x][y - count] == 0) {
            sum_B = Dy[x][y - count];
            break;
        }
        count++;
    }
    sum_B %= MOD;
    sum = (sum_A + sum_B) % MOD;
    return sum;
}
int solution(int m, int n,vector<vector<int> > city_map) {
    int answer = 0;
    init(m,n,city_map);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (city_map[i][j] == 0) {
                Dy[i][j] = path_calc(i, j);
            }
        }
    }
    answer = Dy[m - 1][n - 1];
    return answer;
}