[백준 1577] 도로의 개수

• 문제 : 1577 도로의 개수
• 유형 : DP
• 풀이 : (i,j)에서의 경로의 수를 저장하면서 모든 경우의 수를 재귀적으로 구해준다. 메모이제이션이 없으면 시간초과가 난다. 갈 수 없는 경로는 set에 저장해뒀다가 경로 탐색할 때 확인한다. 주의할 점은 갈 수 없는 경로가 순서대로 들어오지 않기 때문에 정렬을 해주어야 함
• 코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int N, M, k;
set<pair<pair<int, int>, pair<int, int>>> s;

long long dp[101][101];
long long dfs(int r, int c) {
	if (r == M && c == N) {
		return 1;
	}

	long long& ret = dp[r][c];
	if (ret != 0) return ret;

	int nx = c + 1;
	int ny = r;

	if (nx <= N && s.count({ {c,r},{nx,ny} }) == 0) ret += dfs(r, c + 1);

	nx--;
	ny++;

	if (ny <= M && s.count({ {c,r},{nx,ny} }) == 0) ret += dfs(r + 1, c);

	return ret;
}


int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> N >> M >> k;
	for (int i = 0; i < k; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		if (a > c || b > d) {
			swap(a, c); swap(b, d);
		}
		s.insert({ {a,b},{c,d} });
	}

	cout << dfs(0, 0);
	

	return 0;
}