--์ง-- | ------ | ------ | ------ |
---|---|---|---|
------ | ------ | ------ | ------ |
------ | ------ | ------ | -ํ๊ต- |
1. DFS ํ์์ ์ํ(ํจ์ ๋ง๋ค๊ธฐ)
def dfs(y, x, row, col, puddles):
path = [[1, 0], [0, 1]]
answer = 0
1-1. ๋์ ๋๋ฌํ์ ๋ 1์ ๋ฐํ
if [y, x] == [row - 1, col - 1]: return 1
1-2. ์ค๋ฅธ์ชฝ/์๋ ๋ฐฉํฅ์ผ๋ก ์งํ
for i in range(2):
ny = y + path[i][0]
nx = x + path[i][0]
if 0 <= ny < row and 0 <= nx < col:
if [nx + 1, ny + 1] in puddles: continue
answer += dfs(ny, nx, row, col, puddles)
1-3. ์ ๋ต์ 1,000,000,007๋ก ๋๋๋ค.
return answer % 1000000007
2. ์ฒซ dfs() ํจ์๋ฅผ ํธ์ถํ๊ณ ๊ฒฐ๊ณผ๋ฅผ ๋ฐํ
def solution(m, n, puddles):
return dfs(0, 0, n, m, puddles)
def dfs(y, x, row, col, puddles):
path = [[1, 0], [0, 1]]
answer = 0
if [y, x] == [row - 1, col - 1]: return 1
for i in range(2):
ny = y + path[i][0]
nx = x + path[i][0]
if 0 <= ny < row and 0 <= nx < col:
if [nx + 1, ny + 1] in puddles: continue
answer += dfs(ny, nx, row, col, puddles)
return answer % 1000000007
def solution(m, n, puddles):
return dfs(0, 0, n, m, puddles)