[백준 1577번] 도로의 개수 (C++)

문제링크 : https://www.acmicpc.net/problem/1577

1577번: 도로의 개수

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, K, a, b, c, d;

ll dp[101][101];
bool check[202][202];
int dy[2] = {-1, 0};
int dx[2] = {0, -1};

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M >> K;
    
    while(K--)
    {
        cin >> a >> b >> c >> d;
        check[b+d][a+c]=1; //부실공사 표시
    }

    dp[0][0]=1;

    for(int y=0; y<=M; y++)
    {
        for(int x=0; x<=N; x++)
        {
            for(int i=0; i<2; i++)
            {
                int py = y + dy[i];
                int px = x + dx[i];
                if(py < 0 || px < 0 || py > M || px > N) continue; //범위조건
                if(check[py+y][px+x]) continue; //부실공사 체크
                dp[y][x] += dp[py][px]; //이전값 더해주기
            }
        }
    }

    cout << dp[M][N];

    return 0;
}

 

기본적인 dp 식은 이동방향 2가지에 대해 dp[i][j] += dp[i-1][j], dp[i][j] +=dp[i][j-1]이다. (아래->위, 왼->오)

그리고 부실공사를 체크할 배열을 따로 선언해주었다.

 

하지만 위 2가지를 어떻게 활용해야 부실공사하는 부분에 대해서만 dp 갱신을 스킵할 수 있는지 다소 헤매다가 검색을 통해 새로운 방법을 알 수 있었다.

 

bfs 방식을 활용하여 dy, dx를 dp 점화식과 같이 이동하도록 {-1, 0}, {0, -1)로 초기화하여 활용한다.

이후 0~M, 0~N까지 이동하며 현 위치와 그 직전값을 확인해준다.

이를 이용해 부실공사 체크가 가능하다. (좌표 : 직전 y + 현 y, 직전 x + 현 x)

그리고 현 dp[y][x]에 직전 위치 dp에 해당하는 dp[py][px]의 값들 더하며 갱신하게 된다.