BOJ 1577 - 도로의 갯수

www.acmicpc.net/problem/1577

1577번: 도로의 개수

 

(0, 0) 에서 목적지인 (M, N) 으로 최단경로로 이동할때 가능한 경우의 수를 전부 구하는 문제로,

일단 (M, N) 으로 가는 것은 가는 방향의 수가 딱 2개 밖에 없다

오른쪽으로 가거나 밑으로 가거나

 

그래서 dp[i][j] = dp[i][j - 1] + dp[i - 1][j] 라고 볼 수 있다.

 

문제는 공사 중인 도로는 지나갈 수 없기 때문에, 지나갈 수 없는 구간에 대한 표현은 어떻게 해야되는가가

이 문제의 가장 큰 핵심이다.

 

처음에는 DFS 처럼 풀면서 방문할 수 없는 지역들은 미리 방문 불가 지역으로 만들고 경우의 수를 계산하려고 하였으나, 원하는 답을 구해낼 수 없었다.

 

오랜시간 고민하다가 결국 답을 봤는데

방문 처리를 하기 위한 배열을 2배의 크기로 늘려서 선언한다음

입력 받은 두 좌표 쌍 ( (a, b), (c, d) ) 의 합에 해당하는 부분을 미리 방문 처리해주고

(이 위치가 지나갈 수 없는 공사장 좌표)

 

입력을 다 받고 난뒤, DP 배열을 초기화하기 위해,

가로 방향 세로 방향 탐색하면서 공사장 좌표를 지나지 않도록 초기화한다.

 

그리고 나서 DP 배열을 완성해주는데

공사장을 지나치지 않는 부분에 대해서만 경우의 수를 늘리도록 처리를 해준다.

 

- C++

#include <iostream>
 
using namespace std;
 
int N, M, K; // 가로, 세로, 공사 
bool visited[201][201]; // 공사 지역 방문처리 
long long dp[101][101];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> M;
    cin >> K;
    
    for (int i = 0; i < K; ++i) {
        int a, b, c, d; // (a, b) , (c, d)
        cin >> a >> b >> c >> d;
        visited[b + d][a + c] = true; // y, x 순 
    }
    
    dp[0][0] = 1; // 시작 지점으로 가는 경우의 수 1개 
    
    // DP 배열 초기화
    
    // y 축 도로 초기화
    for (int i = 1; i <= M; ++i) {
        if (visited[2 * i - 1][0]) break;
        dp[i][0] = 1;
    } 
    
    // x 축 도로 초기화
    for (int i = 1; i <= N; ++i) {
        if (visited[0][2 * i - 1]) break;
        dp[0][i] = 1;
    }
    
    // O(MN) 으로 돌면서 방문 가능한 지역에 한해서 경우의 수 계산 
    for (int i = 1; i <= M; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (!visited[2 * i - 1][2 * j])
                dp[i][j] += dp[i - 1][j];
                
            if (!visited[2 * i][2 * j - 1])
                dp[i][j] += dp[i][j - 1];
        }
    }
    
    cout << dp[M][N];
    
    return 0;
}