[Algorithm]Baekjoon 1577번 : 도로의 개수

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
 
int n, m, k;
int check[101][101][2] = { false };
unsigned long long dp[101][101] = { 0 };
int dirs[2][2] = { {0,1}, {1,0} };
 
unsigned long long dfs(int y, int x)
{
    unsigned long long& result = dp[y][x];
 
    if (result != -1) return result;
 
    if (y == n && x == m)
    {
        return 1;
    }
 
    result = 0;
 
    for (int i = 0; i < 2; ++i)
    {
        int nextY = y + dirs[i][0];
        int nextX = x + dirs[i][1];
 
        if (nextY > n) continue;
        if (nextX > m) continue;
        if (check[y][x][i]) continue; // 공사 체크
 
        result += dfs(nextY, nextX);
    }
 
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> k;
    
    for (int i = 0; i < k; ++i)
    {
        int a, b, c, d;
 
        cin >> a >> b >> c >> d;
 
        if (a == c) // y값 같으면
        {
            int minX = min(b, d);
            check[a][minX][0] = true;
        }
        else if (b == d) // x값 같으면
        {
            int minY = min(a, c);
            check[minY][b][1] = true;
        }
    }
   
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0);
}
 

 

 

참고로 세준이는 목표를 향한 방향으로만 움직인다.

즉 0,0이 좌상단, n,m이 우하단일 경우 세준이는 오른쪽,아래로만 이동한다.

 

이 문제에서 공사도로의 길이는 무조건 1이라고 못박아놨다.

그래서 도로의 위치가 주어졌을 경우, 특정위치 y,x에서 우측방향의 도로와 아래측방향 도로가 공사중인지 아닌지를 미리 체크해놓는다.

이 때, 큰좌표값에서 작은좌표값으의 방향은 체크할 필요가 없다. 세준이는 오른쪽, 아래로만 이동하기 때문이다.

 

예를 들어 공사좌표 6,6  5,6이 들어왔다고 가정해보자.

 

6,6에서 5,6방향인 윗쪽방향은 체크할 필요없다. 위쪽으로 이동할일은 없기 때문.

그러니 5,6에서 6,6 방향 아래쪽만 체크해주면 된다.

check[5][6][0] = true;  이런식으로 체크해준다.

5,6에서 오른쪽방향은 가면안된다는 뜻이다.