[Python] 백준 1577번 : 도로의 개수

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

1577번: 도로의 개수

---

💡 문제 풀이

DP 문제이다.

 

이 문제는 메모리의 크기는 작긴 하지만 n, m의 100까지므로 배열을 사용해도 괜찮다.

최단거리로만 이동하기 때문에 항상 아래 혹은 오른쪽으로만 이동한다는 점이 포인트이다.

주어진 (a,b), (c,d)에 대해서 어떤 점이 못 가는 점인지 판단하기 까다롭다는 생각에

방향에 따라 이동 가능 여부를 따지려고 4차원 배열까지 가고 마지막 배열에 boolean 값을 넣었다.

 

지날 수 없는 도로를 주어진 좌표가 아무렇게 되어있어 출발좌표 → 도착좌표로 바꿔주고

지날 수 없는 도로를 체크해준다.

 

문제에서 n과 m이 주어졌을 때 인덱싱 때문에 n+1까지 따져야 한다.

따라서 행과 열을 각각 n+1, m+1 만큼 반복을 돌면서 두 방향에 대해서 이동 가능 여부를 확인하고 DP값을 더해주면 된다.

✔️ 느낀 점

나를 믿지 않아 오래 걸린 문제이다. 백준이 맨날 시간제한, 메모리 제한을 두니까 생각나는 대로 구현하지 않으려는 것 같다. 다음부터 조금 더 나를 믿고 구현해야겠다. 

💻 코드

import sys

n, m = map(int, sys.stdin.readline().split())
DP = [[[0,[True,True]] for _ in range(m+1)] for _ in range(n+1)]
DP[0][0][0] = 1

k = int(sys.stdin.readline())
for _ in range(k):
    a,b,c,d = map(int, sys.stdin.readline().split())
    if a > c: a, c = c, a
    if b > d: b, d = d, b
    d = 0 if c-a> d-b else 1
    DP[a][b][1][d] = False
   
moves = [(1,0), (0,1)] 
for x in range(n+1):
    for y in range(m+1):
        for i in range(2):
            nx, ny = x + moves[i][0], y + moves[i][1]
            if nx <= n and ny <= m and DP[x][y][1][i]:
                DP[nx][ny][0] += DP[x][y][0]
                
print(DP[n][m][0])