브루트포스) 17070.파이프 옮기기 1

코딩 테스트/삼성 기출

브루트포스) 17070.파이프 옮기기 1

Carnival7 2022. 10. 3. 17:33

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

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

def dfs(x,y,direction):
    global a,n,ans

    if (x,y)==(n-1,n-1):
        ans+=1
        return

    # 가
    if direction==0:
        # 가로
        if 0<=y+1<n and a[x][y+1]!=1:
            dfs(x,y+1,0)
        # 대각선
        if 0<=x+1<n and 0<=y+1<n and a[x+1][y+1]!= 1 and a[x][y+1]!=1 and a[x+1][y]!=1:
            dfs(x+1,y+1,2)
    # 세로
    elif direction==1:
        # 세로
        if 0 <= x+1 < n and a[x+1][y]!=1:
            dfs(x+1, y,1)
        # 대각선
        if 0 <= x + 1 < n and 0 <= y + 1 < n and a[x+1][y+1]!= 1 and a[x][y+1]!=1 and a[x+1][y]!=1:
            dfs(x + 1, y + 1,2)
    # 대각선
    elif direction==2:
        # 가로
        if 0<=y+1<n and a[x][y+1]!=1:
            dfs(x,y+1,0)
        # 세로
        if 0 <= x+1 < n and a[x+1][y]!=1:
            dfs(x+1, y,1)
        # 대각선
        if 0 <= x + 1 < n and 0 <= y + 1 < n and a[x+1][y+1]!= 1 and a[x][y+1]!=1 and a[x+1][y]!=1:
            dfs(x + 1, y + 1,2)
dfs(x,y,0)
print(ans)