백준 - 17070 : 파이프 옮기기 1 (G5)

 1N = int(input())
 2
 3L = [list(map(int, input().split())) for _ in range(N)]
 4result = 0
 5
 6def dfs(x, y, direc):
 7    global result
 8    if x == N-1 and y == N-1:
 9        result += 1
10        return
11
12    if x+1 < N and y+1 < N and L[y+1][x] == 0 and L[y][x+1] == 0 and L[y+1][x+1] == 0:
13        dfs(x+1, y+1, 2)
14
15    if (direc == 0 or direc == 2) and x+1 < N and L[y][x+1] == 0:
16        dfs(x+1, y, 0)
17
18    if (direc == 1 or direc == 2) and y+1 < N and L[y+1][x] == 0:
19        dfs(x, y+1, 1)
20
21dfs(1, 0, 0)
22print(result)