[C++, python] BOJ, 백준 1577 - 도로의 개수

문제 링크

1577번: 도로의 개수

문제 풀이

이 문제는 [0, 0]에서 최단경로로 [N, M]에 도달하기 위한 방법의 수를 구하는 문제이다. 다들 한번씩 경로에 1을 표시해서 총 몇가지의 길이 존재하는지 문제를 풀어봤을 것이다. 이것을 알고리즘으로는 DP로 풀 수 있다.

공사중인 도로

만약 [1, 1]인 지점으로 가기 위해서는 최단거리이므로 무조건 [0, 1] 혹은 [1, 0]을 통과해야 한다.
따라서 [1, 1]까지의 경로는 [0, 1]까지의 경로와 [1, 0]까지의 경로의 합이 될 것이다.
만약 [0, 1] 혹은 [1, 0] 지점부터 [1, 1]지점까지 공사중이라면, 공사중인 지점을 제외한 나머지 경로만 더해질 것이고, 두 경로 모두 공사중이라면, [1, 1]로 오는 경로는 0이 된다.

이 조건을 코드에 반영하면 된다.

정답코드

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

ll dp[101][101];
int road[101][101][2];
int dy[2]={1,0},dx[2]={0,1};
int N, M, K;

ll sol(int y,int x){
    if(y == N && x == M) return 1;
    ll& ret = dp[y][x];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i < 2; i++){
        if (!road[y][x][i]){
            int ny = y + dy[i], nx = x + dx[i];
            if (ny <= N && nx <= M) ret += sol(ny, nx);
        }
    }
    return ret;
}

int main() {
    fast;
    cin >> N >> M >> K;
    int cnt = 1;
    while (K--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (a > c) swap(a, c);
        else if (b > d) swap(b, d);
        if (a < c) road[a][b][0] = 1;
        else if (b < d) road[a][b][1] = 1;
    }
    memset(dp, -1, sizeof(dp));
    cout << sol(0, 0);
    return 0;
}

python

N, M = map(int, input().split())
K = int(input())
dp = [[0] * (N + 1) for _ in range(M + 1)]
road = []
dp[0][0] = 1
for i in range(K):
    road.append(list(map(int, input().split())))

def check(current, a, b, c, d):
    if current == [a, b, c, d] or current == [c, d, a, b]:
        return True
    else:
        return False

for x in range(M + 1):
    for y in range(N + 1):
        if y > 0:
            for a, b, c, d in road:
                if check([y - 1, x, y, x], a, b, c, d):
                    break
            else:
                dp[x][y] += dp[x][y - 1]
        if x > 0:
            for a, b, c, d in road:
                if check([y, x - 1, y, x], a, b, c, d):
                    break
            else:
                dp[x][y] += dp[x - 1][y]
print(dp[M][N])