백준 17070 파이프 옮기기 1 (파이썬)

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

17070번: 파이프 옮기기 1

dfs 안에 반복문을 넣고 이동하면 시간 초과가 발생했다

 

1. dfs에 (0, 1) 좌표와 shape 변수를 입력한다. shape에서 가로는 0, 세로는 1, 대각선은 2로 표시한다

2. dfs로 이동면서 (n-1, n-1)에 도착하면 횟수를 증가시킨다

3. 다음 이동을 가로, 세로, 대각선으로 이동할 수 있는지 각각 검사한다

   대각선의 경우 4칸을 차지하기 때문에 a[x+1][y], a[x][y+1]에 벽이 없는지 확인해야한다

import sys

input = sys.stdin.readline

def dfs(x, y, shape):
    global ans
    if x == n-1 and y == n-1:
        ans += 1
        return

    if shape == 0 or shape == 2:
        if y + 1 < n:
            if a[x][y+1] == 0:
                dfs(x, y+1, 0)
    if shape == 1 or shape == 2:
        if x + 1 < n:
            if a[x+1][y] == 0:
                dfs(x+1, y, 1)
    if shape == 0 or shape == 1 or shape == 2:
        if x + 1 < n and y + 1 < n:
            if a[x+1][y] == 0 and a[x][y+1] == 0 and a[x+1][y+1] == 0:
                dfs(x+1, y+1, 2)


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
dfs(0, 1, 0)
print(ans)