67)미로 탐색(DFS)

문제

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하기

 

조건

출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다.

 

격자판의 1은 벽이고, 0은 통로이다.

 

격자판의 움직임은 상하좌우로만 움직인다.

 

미로가 다음과 같다면

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

 

제한사항

7*7 격자판의 정보가 주어집니다.

 

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

 

문제풀이

def go(x, y):
  global cnt

  if x==6 and y==6:
    cnt+=1
  else:
    for i in range(4):
      xx=x+dx[i]
      yy=y+dy[i]
      
      if 0<=xx<=6 and 0<=yy<=6 and a[xx][yy]==0:
        a[xx][yy]=1
        go(xx, yy)
        a[xx][yy]=0

dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
a=[list(map(int, input().split())) for _ in range(7)]
cnt=0
a[0][0]=1
go(0, 0)
print(cnt)