누가 봐도 DP 문제. (1, 1)에서 (n, m)까지 갈 수 있는 경로의 수를 구하면 된다. 단 두가지 조건이 추가로 붙는다.
- 아이템(별)을 다 먹어야 함
- 장애물을 지나갈 수 없음
이 두 조건에 대한 해결법으로 아래와 같은 방법을 제시했다.
- 지금까지 먹은 아이템을 저장하는 2차원 배열을 하나 더 생성하여 저장, 경로 판단시 사용.
다만 구현의 편의를 위해(?) 하나의 2차원list에tuple로 몰아넣었다... - 장애물 칸은 이전 칸들의 값과 관계없이 0으로 설정.
별의 갯수를 이용해 가능한 경로의 가지수를 판단하는 방식은 아래와 같다
- 아래에서 올라오는 경로의 별이 많은 경우 -> 아래 칸의 경로의 수를 그대로 가져옴
- 왼쪽에서 오는 경로의 별이 많은 경우 -> 왼쪽 칸의 경로의 수를 그대로 가져옴
- 같은 경우 -> 양 쪽의 경로의 수를 합쳐서 가져옴
이 외에도 별이 있는 곳을 지나면 별의 값을 1 더해서 저장하였고, 좌표 (1, 1)이 (1, 0)으로 시작하게 하기 위해서 좌표 (0, 1)의 값을 (1, 0)으로 설정해주었다.
아무튼 예제로 주어진 값을 입력하면 아래와 같은 결과가 나온다. (편의를 위해 상하반전 함)
[(0, 0), (1, 0), (3, 0), (1, 1), (5, 1), (2, 3), (4, 3), (2, 4), (4, 4)]
[(0, 0), (1, 0), (2, 0), (1, 1), (4, 1), (2, 3), (2, 3), (2, 4), (2, 4)]
[(0, 0), (1, 0), (1, 0), (1, 1), (3, 1), (2, 3), (0, 0), (0, 0), (0, 0)]
[(0, 0), (1, 0), (0, 0), (1, 1), (2, 1), (2, 2), (2, 2), (0, 0), (0, 0)]
[(0, 0), (1, 0), (1, 1), (1, 1), (1, 1), (0, 0), (0, 0), (0, 0), (0, 0)]
[(0, 0), (1, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)]
즉 최종적으로 4개의 별을 4개 경로로 먹을 수 있다는 결과가 나온다.