깊이우선탐색 지도탐색 알고리즘

DFS_MapSearching.py

class DFS_MapSearching:
    def __init__(self):
        self.row, self.col = list(map(int, input("행, 열:").split()))
        self._map = [[0] * self.row for _ in range(self.col)]
        self._min = self.row * self.col

        print("탐색할 지도:")
        for i in range(self.col):
            for j in range(self.row):
                self._map[i][j] = 1
                print(self._map[i][j], end=" ")
            print("")

        # 생성된 배열공간은 row 까지인데 탐색은 row + 1 까지하므로, 오버플로우 방지할 수 있도록 -1씩 해줌
        self.row -= 1
        self.col -= 1

        self.dfs(0, 0, 0)
        print("최단 거리 : %d" % self._min)

    def dfs(self, x, y, length):
        if x is self.row and y is self.col:
            if self._min > length:
                self._min = length
                return

        self._map[y][x] = 0

        # 오른쪽 아래 대각선 이동
        if y < self.col and x < self.row and self._map[y + 1][x + 1] is 1:
            self.dfs(x + 1, y + 1, length + 1)

        # 왼쪽 이동
        if x > 0 and self._map[y][x - 1] is 1:
            self.dfs(x-1, y, length+1)
        # 오른쪽 이동
        if x < self.row and self._map[y][x + 1] is 1:
            self.dfs(x+1, y, length+1)
        # 아래로 이동
        if y < self.col and self._map[y + 1][x] is 1:
            self.dfs(x, y+1, length+1)
        # 위로 이동
        if y > 0 and self._map[y - 1][x] is 1:
            self.dfs(x, y-1, length+1)

        self._map[y][x] = 1


DFS_MapSearching()

##
행, 열:5 5
탐색할 지도:
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
최단 거리 : 4
##

TODO: change DFS to BFS
TODO: change recursion to memoization