[BOJ] 1577. 도로의 개수

문제

---

길 찾기 문제. (N+M)! / N! M! 으로 구할 수도 있겠지만 DP 를 사용했다.

포인트

---

막힌 길을 찾기 위해 3차원 배열을 사용하였으며, 오른쪽으로 막힌 것은 마지막 배열의 index 1, 위쪽으로 막힌 것은 마지막 배열의 index 2를 통해 표시했다. 대각으로만 움직이기에 posX, posY 를 이용해 posX–, posY++ 하다가 끝을 만나면 위로 다시 올려 줘서 반복을 줄일 수 있을 것 같다.

코드

---

n, m = map(int,input().split())
k = int(input())

constructions = []

matrix = [[[0, 0, 0]for _ in range(m + 1)] for _ in range(n + 1)]

for i in range(k):
    constructions.append(list(map(int, input().split())))
    if constructions[i][0] == constructions[i][2]:
        x = constructions[i][0]
        y = min(constructions[i][1], constructions[i][3])
        matrix[x][y][1] = 1
    else:
        x = min(constructions[i][0], constructions[i][2])
        y = constructions[i][1]
        matrix[x][y][2] = 1

matrix[0][0][0] = 1
for i in range(1, n + m + 1):
    for j in range(i + 1):
        if j > n or i - j > m:
            continue
        if j == 0:
            if matrix[0][i-1][1] == 0:
                matrix[j][i - j][0] = matrix[0][i-1][0]
        elif j == i:
            if matrix[i-1][0][2] == 0:
                matrix[j][i-j][0] = matrix[i-1][0][0]
        else:
            if matrix[j - 1][i-j][2] == 0:
                matrix[j][i-j][0] += matrix[j - 1][i-j][0]
            if matrix[j][i-j-1][1] == 0:
                matrix[j][i-j][0] += matrix[j][i-j-1][0]


print(matrix[n][m][0])