[알고리즘] 미로탐색(DFS)

(문제) 미로탐색(DFS)

---

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

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

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

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

미로가 다음과 같다면

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

입력설명

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

출력설명

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

테스트케이스

입력예제	출력예제
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	8
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 1 0 1 0 0 0 0 0 0	2
0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0	46
0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0	24
0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0	8
0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 1 0 0 0 0	14

---

해결방법

1. 상, 하, 좌, 우를 나타내는 x좌표와 y좌표를 가지는 리스트를 생성
2. 미로에서 들린 좌표를 저장하는 리스트 생성.
3. DFS를 이용하여 앞으로 한칸씩 전진한다.
4. 만약 좌표가 6과 6이 될 경우 return을 하여 count를 +1 하고 뒤로 되돌아간다.

   동작 시각화

아래의 그림과 같이 모든 길을 전부 들린다.

만약 막혀있는 길이면 다시 뒤로 되돌아 가면서 다른 길을 찾는다.

(제작하는데 있어서 힘들어 몇몇개의 동작만 만들어 보았다!)

---

코드

def DFS(L, x, y):
    global count
    if x == 6 and y == 6:
        count = count + 1
        return
    else:
        for i in range(4):
            if 0 <= dx[i] + x < 7 and 0 <= dy[i] + y < 7:
                if ch_miro[x+dx[i]][y+dy[i]] == 0:
                    if miro[x+dx[i]][y+dy[i]] == 0:
                        ch_miro[x+dx[i]][y+dy[i]] = 1
                        DFS(L+1, x+dx[i], y+dy[i])
                        ch_miro[x+dx[i]][y+dy[i]] = 0

# 상, 우, 하, 좌
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

# 미로 생성
miro = [list(map(int, input().split())) for _ in range(7)]

ch_miro = [[0] * 7 for _ in range(7)]

ch_miro[0][0] = 1

count = 0

DFS(0, 0, 0)

print(count)