[백준 - Python] 1577 - 도로의 개수

0.  문제 링크

 

 

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

1577번: 도로의 개수

---

1.  풀이 방법

 

 

일단 맨 처음에는 BFS로 문제를 풀었는데, 시간 초과, 메모리 초과가 발생하였다.

BFS가 아님을 깨달았고, 고등학교의 확통에서 비슷한 문제를 풀었던 경험이 생각났다.

현재 위치로 올 수 있는 애는 내 좌측과 위이므로, 좌측과 위로 갈 수 있는 경우의 수를 더하면 현재 위치에 도달할 수 있다.는 것이 확통에서 문제를 푼 방법이다.

물론 조합을 사용해서 풀 수 있지만.

 

아무튼 중요한 건 현재 위치로 오는 경우의 수를 알기 위해서는? 좌측, 위쪽에 도달 가능한 경우의 수를 알아야 한다.

그러면 좌측, 위쪽에 도달 가능한 경우의 수는? 이 정도까지 오면 이 문제는 DP라는 것을 알 수 있다.

 

내가 사용한 알고리즘은 다음과 같다.

1. (0, 0)을 경우의 수 1로 두고, 시작한다.
2. (1, 0)에 도달했을 때, (1, 0)은 (0, 0)에서만 올 수 있으므로 (0, 0)의 숫자를 '그대로' 가져온다.
3. 마찬가지로 (0, 1)도 그렇게 하면 된다.
4. (1, 1)은 (0, 1)과 (1, 0)의 경우의 수를 더하면 된다.
5. (4, 5)에서 (5, 5)로 가는 길이 막혔다면, (5, 5)에서 더할 때, (5, 4)만 더하면 된다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n, m = map(int, input().split())
    k = int(input())

    maps = [[0] * (m + 2) for _ in range(n + 2)]        # 패딩 처리
    maps[1][1] = 1

    end = set()
    load = set()

    for _ in range(k):
        a, b, c, d = map(int, input().split())
        (a, b), (c, d) = sorted([(a + 1, b + 1), (c + 1, d + 1)])       # 시작 위치, 끝 위치를 정렬
        end.add((c, d))     # 공사 도로의 끝 지점
        load.add((a, b, c, d))      # 길을 저장해놔야 함

    for y in range(1, n + 2):
        for x in range(1, m + 2):
            if y == 1 and x == 1: continue      # 시작 지점은 일단 제외하고 시작

            if (y, x) in end:       # 공사 도로의 끝 지점이라면
                if (y - 1, x, y, x) not in load:     # 시작 지점을 빼고 더하면 됨
                    maps[y][x] = maps[y - 1][x]
                elif (y, x - 1, y, x) not in load:       # 시작 지점을 뺴고 더하면 됨
                    maps[y][x] = maps[y][x - 1]
            else:
                maps[y][x] = maps[y - 1][x] + maps[y][x - 1]

    print(maps[n + 1][m + 1])

---

3.  마무리