[인프런] 미로탐색

---

문제설명

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

 

 

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

입력조건

• 7 by 7의 격자판이 주어진다.

출력조건

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

사고과정

• 경로의 총 가지수를 구하는 것이므로 DFS를 활용해야 한다. 처음에 입력 인풋을 잘 못 넣어서 시간을 낭비했다...윾
• 어쩄건 백 트래킹을 활용해서 잘 구현해주었다!

풀이

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

def dfs(x, y):
    global cnt
    if x == 6 and y == 6:
        cnt += 1
        return
    else:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < 7 and 0 <= ny < 7 and arr[nx][ny] == 0:
                arr[nx][ny] = 1
                dfs(nx, ny)
                arr[nx][ny] = 0

dfs(0, 0)
print(cnt)