백준 1577 도로의 개수 파이썬

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

1577번: 도로의 개수

 

처음에는 중학생 때인가 배웠던 것처럼 대각선으로 올라가면서 구해야 하기 때문에 그대로 구현해야 한다고 생각했다.

그런데 N*M이기 때문에 행렬이 ㅁ자라고 생각했을 때 ㄴ자로 시작하여 대각선으로 올라가면서 구했다.

 

import sys

N, M = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())

working = set()
for _ in range(K):
    a, b, c, d = map(int, sys.stdin.readline().split())
    if a < c:
        working.add((a, b, c, d))
    elif c < a:
        working.add((c, d, a, b))
    if b < d:
        working.add((a, b, c, d))
    elif b > d:
        working.add((c, d, a, b))

dp = [[0] * (M + 1) for _ in range(N + 1)]
dp[0][0] = 1

for y in range(1, N + 1):
    ty = y
    tx = 0
    while ty >= 0 and tx <= M:
        if ty - 1 >= 0 and (ty - 1, tx, ty, tx) not in working:
            dp[ty][tx] += dp[ty - 1][tx]
        if tx - 1 >= 0 and (ty, tx - 1, ty, tx) not in working:
            dp[ty][tx] += dp[ty][tx - 1]
        ty -= 1
        tx += 1
for x in range(1, M + 1):
    ty = N
    tx = x
    while ty >= 0 and tx <= M:
        if ty - 1 >= 0 and (ty - 1, tx, ty, tx) not in working:
            dp[ty][tx] += dp[ty - 1][tx]
        if tx - 1 >= 0 and (ty, tx - 1, ty, tx) not in working:
            dp[ty][tx] += dp[ty][tx - 1]
        ty -= 1
        tx += 1
print(dp[-1][-1])

 

그런데 생각해보면 (y, x)에 영향을 주는 값은 값의 왼/위쪽 뿐이다.

 

즉, 왼 -> 오, 아래 -> 위 방향으로 채워나가면 굳이 대각선으로 하지 않더라도 같은 결과를 얻을 수 있다.

import sys

N, M = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())

working = set()
for _ in range(K):
    a, b, c, d = map(int, sys.stdin.readline().split())
    if a < c:
        working.add((a, b, c, d))
    elif c < a:
        working.add((c, d, a, b))
    if b < d:
        working.add((a, b, c, d))
    elif b > d:
        working.add((c, d, a, b))

dp = [[0] * (M + 1) for _ in range(N + 1)]
dp[0][0] = 1

for x in range(M + 1):
    for y in range(N + 1):
        if y - 1 >= 0 and (y - 1, x, y, x) not in working:
            dp[y][x] += dp[y - 1][x]
        if x - 1 >= 0 and (y, x - 1, y, x) not in working:
            dp[y][x] += dp[y][x - 1]

print(dp[-1][-1])