🔥

문제

북극곰 윌리는 N × N 격자미로에 갇혀 있다. 미로의 시작점은 가장 왼쪽 위 점이고, 미로의 도착점은 가장 오른쪽 아래 점이다. 미로는 길과 벽으로 이루어져 있다. 길은 .으로 표시되고, 벽은 * 로 표시된다. 북극곰 윌리는 길은 지나갈 수 있지만 벽은 지나갈 수 없고, 북극곰 윌리는 오른쪽이나 아래쪽으로만 이동할 수 있다. 북극곰 윌리가 미로의 시작점에서 출발해 도착점까지 갈 때 가능한 경로의 수를 구해보자.

입력

첫째 줄에 격자의 가로, 세로의 길이 N이 주어진다. (1 ≤ N ≤ 1000)

출력

첫째 줄에 북극곰 윌리가 찾을 수 있는 경로의 수를 10^9 - 7로 나눈 나머지를 출력한다.

예제 1 입력

4
....
.*..
...*
*...

예제 1 출력

3

Source

import sys

n = int(input())
arr = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
	arr[i] = sys.stdin.readline().rstrip()

dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][1] = 1
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if(arr[i - 1][j - 1] == '*'):
			continue
		dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007

print(dp[n][n])

참고