[C++, python] BOJ, 백준 5569 - 출근 경로

문제 링크

5569번: 출근 경로

문제 풀이

이번 문제는 최단거리 경로 찾기이다. 추가적으로 제약사항이 존재하는데, "이 도시는 교통 사고를 줄이기 위해서 교차로를 돈 차량은 그 다음 교차로에서 다시 방향을 바꿀 수 없다. 즉, 교차로에서 방향을 바꾼 후, 1 블록만 이동한 후 다시 방향을 바꿀 수 없다." 라고 한다.

따라서 이 경우, 동쪽과 북쪽(x, y 방향이라고 하자)방향으로만 이동해 2가지의 방향이라고 생각할 수 있지만, x방향으로 바꿀 수 있는지의 유무, y방향으로 바꿀 수 있는지의 유무에 따라 총 4가지의 방향으로 생각해야 한다.

• 첫 번째 인자가 0인 경우 x 방향으로 이동, 1인 경우 y 방향으로 이동
• 두 번째 인자가 0인 경우 현재 방향으로 1칸만 이동, 1인 경우 2칸 이상 이동

정답 코드

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define ll long long

// 0 : 꺾을 수 있음. 1 : 꺾을 수 없음
int dp[110][110][2][2]; //dir, 1 or over2
int ans = 0, w, h, mod = 100000;

int main(){
    fast;
    cin >> w >> h;

    for (int i = 2; i <= w; i++) dp[i][1][0][0] = 1;
    for (int i = 2; i <= h; i++) dp[1][i][1][0] = 1;
    for (int i = 2; i <= w; i++) {
        for (int j = 2; j <= h; j++) {
            dp[i][j][0][0] = (dp[i-1][j][0][0] + dp[i-1][j][0][1]) % mod;
            dp[i][j][0][1] = dp[i-1][j][1][0];
            dp[i][j][1][0] = (dp[i][j-1][1][0] + dp[i][j-1][1][1]) % mod;
            dp[i][j][1][1] = dp[i][j-1][0][0];
        }
    }
    for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) ans += dp[w][h][i][j];
    cout << ans % mod;
}

python

w, h = map(int, input().split())
mod = 100000
dp = [[[[0] * 2 for _ in range(2)] for _ in range(101)] for _ in range(101)]
for i in range(2, w + 1) :
    dp[i][1][0][0] = 1
for i in range(2, h + 1) :
    dp[1][i][1][0] = 1
for i in range(2, w + 1) :
    for j in range(2, h + 1) :
        dp[i][j][0][0] = (dp[i - 1][j][0][0] + dp[i - 1][j][0][1]) % mod;
        dp[i][j][0][1] = dp[i - 1][j][1][0];
        dp[i][j][1][0] = (dp[i][j - 1][1][0] + dp[i][j - 1][1][1]) % mod;
        dp[i][j][1][1] = dp[i][j - 1][0][0];
ans = 0
for i in range(2) :
    for j in range(2) :
        ans += dp[w][h][i][j]
print(ans % mod)