첫째 줄에 도로의 가로 크기 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보다 크거나 같고, 2^63-1보다 작거나 같은 자연수이다.
입력 예시
6 6
2
0 0 0 1
6 6 5 6
출력 예시
252
풀이
DP를 이용하면 되는 간단한 문제. 최단 경로를 무조건 이용하므로, (x, y) 좌표에서는 무조건 (x-1, y) 혹은 (x, y-1)좌표에서부터 진행되며 그 다음으로 (x+1, y) 혹은 (x, y+1)좌표로 나가게 된다.
문제는 공사 도로 케이스. 공사 도로인 입력은 배제해야 한다. 즉 (x, y)의 경우의 수를 따질 때 (x-1, y) 그리고 (x, y-1)에서의 경우의 수를 각각 합하되, 이 좌표값들이 공사 도로인 입력일 경우는 제외하도록 코드를 작성하면 된다.
풀이 코드
from collections import defaultdict
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
K = int(input())
construct_dict = defaultdict(set)
for _ in range(K) :
a, b, c, d = map(int, input().split())
construct_dict[(a, b)].add((c, d))
construct_dict[(c, d)].add((a, b))
dp = [[0]*(N+1) for _ in range(M+1)]
dp[0][0] = 1
for y in range(M+1) :
for x in range(N+1) :
if y > 0 and ((x, y) not in construct_dict or (x, y-1) not in construct_dict[(x, y)]) :
dp[y][x] += dp[y-1][x]
if x > 0 and ((x, y) not in construct_dict or (x-1, y) not in construct_dict[(x, y)]) :
dp[y][x] += dp[y][x-1]
print(dp[-1][-1])