065 - 미로탐색(DFS)

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격 자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

 

 

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

 

 

▣ 입력설명
7*7 격자판의 정보가 주어집니다.

 

▣ 출력설명
첫 번째 줄에 경로의 가지수를 출력한다.

 

▣ 입력예제 1

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0

 

▣ 출력예제 1

8

 

 

 

#import sys
#sys.stdin = open('in5.txt', 'rt')


def DFS(x1, y1):
    global cnt

    if x1 == 6 and y1 == 6:
        cnt += 1
        # print(f'cnt:{cnt}')
        # for x in a:
        #     print(x)
        return
    else:
        for i in range(4):
            x = x1+dx[i]
            y = y1+dy[i]
            if 0 <= x <= 6 and 0 <= y <= 6 and a[x][y] == 0:
                a[x][y] = 2
                DFS(x, y)
                a[x][y] = 0


if __name__ == '__main__':
    a = [list(map(int, input().split())) for _ in range(7)]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    # for x in a:
    #     print(x)
    a[0][0] = 1
    cnt = 0
    DFS(0, 0)
    print(f'{cnt}')