17070번 파이프 옮기기 1(DFS)

#문제링크 : https://www.acmicpc.net/problem/17070

a : 타일 배열 / state : 0(가로) 1(대각선) 2(세로) / cnt : 가능한 경우의 수

전략 : 시작은 (0, 1)에서 시작합니다. 가로로 가기위해서는 (row, col+1)의 타일이 빈칸이어야 하므로, 해당 조건을 만족하면 다음 뎁스(칸)로 넘어가서 DFS를 실시합니다. 대각선으로 가기위해서는 (row, col+1), (row+1, col+1), (row+1, col) 세개의 타일이 빈칸이어야 하고 조건을 충족하면 다음 뎁스(칸)로 넘어가서 DFS를 실시합니다. 세로로 가기위해서는 (row+1, col)의 타일이 빈칸이어야 하므로, 해당 조건을 만족하면 다음 뎁스(칸)로 넘어가서 DFS를 실시합니다.

※주의사항

1. 배열의 행과 열의 인덱스 크기는 N보다 작아야합니다.

2. DFS를 마치고 백트래킹된 상태에서의 조건을 잘 설정해줘야 합니다.

3. state별로 움직일 수 있는 조건이 다 다르므로 DFS를 들어갈때와 나올때 해당 조건을 작성해줘야 합니다.