Algorithm - 미로 탐색(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[미로 탐색(DFS)]

 

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

 

격자판의 움직임은 상하좌우로만 움직이며 미로가 아래와 같다면 위의 지도의 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다. 참고로, 격자판의 1은 벽이고 0은 통로이다. 

 

7*7 격자판

 

*입력 설명

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

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_65.txt', 'rt')

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def DFS(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 board[xx][yy] == 0:
                board[xx][yy] = 1
                DFS(xx, yy)
                board[xx][yy] = 0

if __name__ == "__main__":
    board = [list(map(int, input().split())) for _ in range(7)]
    cnt = 0
    board[0][0] = 1
    DFS(0, 0)
    print(cnt)
    
# 출력 : 8

 

input_65.txt(입력)

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. 변수 xx와 yy는 DFS 탐색을 통해 앞으로 탐색할 방향을 의미한다. (단, 시계방향으로 탐색을 진행함)
2. board[0][0] = 1 코드는 경로탐색의 시작점이 격자판의 (0, 0) 지점이라는 것을 의미한다.
3. DFS 탐색으로 이미 지나간 경로는 격자판의 값이 1이 되도록 만들어줘야 한다. (경로탐색의 중복을 방지하기 위함)
4. 즉, 이미 지나간 경로는 1을 채워넣어 벽으로 간주되도록 만들고 이후에 다시 방문해야 할 경로는 0으로 되돌려 길로 간주되도록 만들어야 한다.
5. 또한, 다른 경우의 수를 고려하기 위해 이미 지나갔던 경로를 되돌아갈 경우 해당 경로의 격자판 값은 다시 0으로 초기화 시켜줘야 한다. (ex. board[xx][yy] = 0)