# 클래스로 구현하는 스택

class ArrayStack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.array = [None] * self.capacity
        self.top = -1

        # 스택의 연산들을 맴버 함수로 구현

    def isEmpty(self):
        return self.top == -1
    
    def isFull(self):
        return self.top == self.capacity - 1

    def push(self, e) :
        if not self.isFull():
            self.top += 1
            self.array[self.top] = e
        else: pass
    
    def pop(self):
        if not self.isEmpty():
            self.top -= 1
            return self.array[self.top + 1]
        else: pass

    def peek(self):
        if not self.isEmpty():
            return self.array[self.top]
        else: pass


    def __str__(self):
        return str(self.array[:self.top+1])

# DFS 로 미로의 출구 찾기

map = [['1', '1', '1', '1', '1', '1'],
       ['e', '0', '1', '0', '0', '1'],
       ['1', '0', '0', '0', '1', '1'],
       ['1', '0', '1', '0', '1', '1'],
       ['1', '0', '1', '0', '0', 'x'],
       ['1', '1', '1', '1', '1', '1']]


MAZE_SIZE = 6

# 갈 수 있는 위치인지 확인
def isValid(x, y):
    if 0 <= x < MAZE_SIZE and 0 <= y < MAZE_SIZE:
        if map[x][y] == '0' or map[x][y] == 'x':
            return True
    return False

# DFS 로 미로 찾기
def DFS():
    print('DFS: ')
    stack = ArrayStack(100)
    stack.push((0, 1))

    while not stack.isEmpty():
        here  = stack.pop()
        print(here, end='->')
        (x, y) = here

        if (map[y][x] == 'x') :
            return True
        else:
            map[y][x] = '.'
            if isValid(x, y-1): stack.push((x, y-1))
            if isValid(x, y+1): stack.push((x, y+1))
            if isValid(x-1, y): stack.push((x-1, y))
            if isValid(x+1, y): stack.push((x+1, y))
        print('현재 스택: ', stack)
    return False

# Test
result = DFS()
if result: print(' --> 미로탐색 성공')
else: print(' --> 미로탐색 실패')

map[y][x] = '.'
            if isValid(x, y-1): stack.push((x, y-1)) # 상
            if isValid(x, y+1): stack.push((x, y+1)) # 하 
            if isValid(x-1, y): stack.push((x-1, y)) # 좌
            if isValid(x+1, y): stack.push((x+1, y)) # 우 

# DFS 로 미로의 출구 찾기

map = [['1', '1', '1', '1', '1', '1'],
       ['e', '0', '1', '0', '0', '1'],
       ['1', '0', '0', '0', '1', '1'],
       ['1', '0', '1', '0', '1', '1'],
       ['1', '0', '1', '0', '0', 'x'],
       ['1', '1', '1', '1', '1', '1']]


MAZE_SIZE = 6

# 갈 수 있는 위치인지 확인
def isValid(x, y):
    if 0 <= x < MAZE_SIZE and 0 <= y < MAZE_SIZE:
        if map[x][y] == '0' or map[x][y] == 'x':
            return True
    return False

# DFS 로 미로 찾기
def DFS():
    print('DFS: ')
    stack = []
    stack.append((0, 1))

    while stack:
        here  = stack.pop()
        print(here, end='->')
        (x, y) = here

        if (map[y][x] == 'x') :
            return True
        else:
            map[y][x] = '.'
            if isValid(x, y-1): stack.append((x, y-1))
            if isValid(x, y+1): stack.append((x, y+1))
            if isValid(x-1, y): stack.append((x-1, y))
            if isValid(x+1, y): stack.append((x+1, y))
        print('현재 스택: ', stack)
    return False

# Test
result = DFS()
if result: print(' --> 미로탐색 성공')
else: print(' --> 미로탐색 실패')