[BOJ][C++] 백준 1577번: 도로의 개수

https://www.acmicpc.net/problem/1577

 

문제

세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다.

따라서, 아래 그림과 같이 생겼다.

세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다.

세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다.

(0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자연수이다. 셋째 줄부터 K개 줄에는 공사중인 도로의 정보가 a b c d와 같이 주어진다. a와 c는 0보다 크거나 같고, N보다 작거나 같은 자연수이고, b와 d는 0보다 크거나 같고, M보다 작거나 같은 자연수이다. 그리고, (a, b)와 (c, d)의 거리는 항상 1이다.

출력

첫째 줄에 (0, 0)에서 (N, M)까지 가는 경우의 수를 출력한다. 이 값은 0보다 크거나 같고, 263-1보다 작거나 같은 자연수이다.

 

풀이

dp[i][j] : (i,j) 까지 가는 최단 경로의 갯수

dp[i][j] = dp[i-1][j] + dp[i][j-1]

다이나믹 프로그래밍 기본 문제

 

이 문제의 쟁점은 지나갈 수 없는 도로의 존재를 어떻게 반영하느냐다.

그리고 이 도로에 대한 정보를 시작점과 도착점이라는 괴상한 방식으로 입력을 받는다

필자는 road[i][j][] 형태의 삼중배열로 도로를 지날 수 있는지의 여부를 넣어뒀다

 

road[i][j][0] = (i-1, j)에서 (i,j)로 갈 수 있는지 여부 => 세로(아래쪽 방향) 도로

road[i][j][1] = (i, j-1)에서 (i,j)로 갈 수 있는지 여부 => 가로(오른쪽 방향) 도로

 

그리고 입력은 시작점과 도착점의 위치의 순서를 따로 정해서 주는게 아니기 때문에

공사중인 도로 정보를 입력 받아서 시작점과 도착점을 명확히 하고

방금 받은 도로가 road[i][j][0] 인지 road[i][j][1]인지 잘 표시해야한다

    for(int i=0; i<k; i++) {
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        if(a*100+b > c*100+d) {
            int tmp;
            tmp=a; a=c; c=tmp;
            tmp=b; b=d; d=tmp;
        }
        if(a==c) {
            road[c][d][1] = false;
        } else {
            road[c][d][0] = false;
        }
    }

 

입력이 잘 되었다면 이후 dp 풀이는 쉽다.

기본적으로 dp[i][j] = dp[i-1][j] + dp[i][j-1] 지만

위에서 오는 도로가 막혔다면 dp[i-1][j]를 더하지 않고

왼쪽에서 오는 도로가 막혔다면 dp[i][j-1]를 더하지 않으면 된다.

    // Dp 풀이
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(road[i][j][0]) {
                dp[i][j] += dp[i-1][j];
            }
            if(road[i][j][1]) {
                dp[i][j] += dp[i][j-1];
            }
        }
    }

 

코드

//풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> ci;
typedef long long ll;

const int INF = 101;
bool road[INF][INF][2];

int main() {
    // road 초기화
    for(int i=0; i<INF; i++) {
        for(int j=0; j<INF; j++) {
            road[i][j][0] = true;
            road[i][j][1] = true;
        }
    }
    
    // 입력
    int n, m, k;
    cin >> n >> m >> k;
    for(int i=0; i<k; i++) {
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        if(a*100+b > c*100+d) {
            int tmp;
            tmp=a; a=c; c=tmp;
            tmp=b; b=d; d=tmp;
        }
        if(a==c) {
            road[c][d][1] = false;
        } else {
            road[c][d][0] = false;
        }
    }
    
    // dp 초기화
    vector<vector<ll>>dp(n+1, vector<ll>(m+1, 0));
    dp[0][0] = 1;
    for(int i=1; i<=n; i++) {
        if(road[i][0][0]) {
            dp[i][0] = 1;
        } else {
            break;
        }
    }
    for(int j=1; j<=m; j++) {
        if(road[0][j][1]) {
            dp[0][j] = 1;
        } else {
           break;
        }
    }
    
    // Dp 풀이
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(road[i][j][0]) {
                dp[i][j] += dp[i-1][j];
            }
            if(road[i][j][1]) {
                dp[i][j] += dp[i][j-1];
            }
        }
    }
    
    // 출력
    cout << dp[n][m];
    
    return 0;
}