[백준] 17070. 파이프 옮기기 1

DFS방식으로 풀었다.

파이프가 가로일경우에 다음으로 밀 수 있는 경우가 가로, 대각선

세로일 경우 세로, 대각선

대각선일 경우 가로, 세로, 대각선

이 방법으로 밀 수 있다. 그래서 경우를 나눠서 탐색을 했다.

---

 

def move(x, y, shape): #shape :1가로 2:세로 3:대각선
    global cnt

    if x == N-1 and y == N-1:
        cnt += 1
        return

    if shape == 1: #가로라면
        if y+1 <= N-1 and squre[x][y+1] == 0: #가로
            move(x, y+1, 1)
        if x+1 <= N-1 and y+1 <= N-1 and squre[x+1][y] == 0 and squre[x][y+1] == 0 and squre[x+1][y+1] == 0: #대각선
            move(x+1, y+1, 3)
    elif shape == 2: #세로라면
        if x+1 <= N-1 and squre[x+1][y] == 0: #세로
            move(x+1, y, 2)
        if x+1 <= N-1 and y+1 <= N-1 and squre[x+1][y] == 0 and squre[x][y+1] == 0 and squre[x+1][y+1] == 0: #대각선
            move(x+1, y+1, 3)
    elif shape == 3: #대각선이라면
        if y+1 <= N-1 and squre[x][y+1] == 0: #가로
            move(x, y+1, 1)
        if x+1 <= N-1 and squre[x+1][y] == 0: #세로
            move(x+1, y, 2)
        if x+1 <= N-1 and y+1 <= N-1 and squre[x+1][y] == 0 and squre[x][y+1] == 0 and squre[x+1][y+1] == 0: #대각선
            move(x+1, y+1, 3)




N = int(input())

squre = [list(map(int, input().split(' ')))for _ in range(N)]

cnt = 0
move(0, 1, 1) #처음은 항상 가로 파이프는 (0,0)과 (0,1)에 걸쳐져 있다

print(cnt)