스택

LIFO: Last in, First out

• 설거지 그릇 쌓아놓고 윗 접시만 쓰는 것과 동일한 이치
• 가장 최근에 추가된 자료가 가장 먼저 삭제되는 구조
• 배열로 구현을 하게 되면 오른쪽 끝에서 추가, 삭제가 이루어짐. (설거지 더미를 오른쪽 90도 돌린다고 생각하기)
• 장점: 구현이 간단하며 자료의 추가, 삭제 연산이 빠름.
• 단점: 크기가 제한될 수 있고 중간에 있는 항목을 바로 접근할 수 없음.

push(e) 새로운 요소 e를 삽입
pop() 가장 최근 요소 꺼내서 반환
isEmpty() 스택이 비어있는지 확인

코드

class Stack :
      def __init__( self ):   
            self.s_list = [] #스택 저장 공간을 빈 리스트로 생성한다.    
            
      def push(self, data) :  #push는 삽입할 자료(값)를 필요로 한다.
            self.s_list.append(data)
      def pop(self) :
            if not self.isEmpty() : #빈 상태가 아니라면
                  return self.s_list.pop() #가장 마지막에 삽입된 자료(값)을 반환하여 삭제한다.
      def isEmpty(self) :
            return len(self.s_list) == 0  #s.list의 길이가 0이면 빈 상태를 의미한다.
      def size(self) :
            return len(self.s_list)
      def clear(self) :
            self.s_list = []
      def show(self):
            print(self.s_list)

(중요하지 않음)
이론 상으로는 자료 삽입/삭제가 이루어지는 위치가 왼쪽이든 오른쪽이든 상관없지만, 왼쪽 앞에서 이루어지게 되면 삽입/삭제에 따라 모든 원소가 대거 이동해야 하기 때문에 시간복잡도가 O(n)이 되어버려서 매우 비효율적이게 됨. 따라서 오른쪽에서 하면 O(1)이기 때문에 리스트의 가장 끝에서 하는 것.

---

DFS

스택은 입력의 반대 순으로 출력하여 사용하는 경우에 용이하기 때문에 DFS에 활용된다.

DFS의 ''depth'' 라 함은 갈 수 있는 한 끝까지 경로를 탐색하다가, 막혀 있으면 다시 되돌아온다는 뜻.

모든 경우의 수를 탐색할 때 용이한 방법이기 때문에 최단 경로, 최적 경로 찾는 문제에 쓰이진 못할 듯. 대신 모든 경우의 수 찾기, 모든 조합 만들기 등의 문제에 적용 가능함!

예전에 헷갈렸던건 사람처럼 생각해서 갔던 길 다시 고대로 돌아와야 경로를 저장할 수 있다고 생각해서 (4,0)에 있다가 바로 (1,2)로 이동하는걸 이해를 못했는데 이제 보니 헨젤과 그레텔처럼 갔던 길 다시 되돌아올 필요 없이 그냥 좌표상으로 간 표시만 하면 되는거였음. -> 컴퓨터처럼 사고하기!

내 맘대로 써보는 DFS 수도코드

def DFS(start, end, grid):
    stack = []
    stack.push(start)
    while len(stack) != 0:
        pos = stack.pop()
        if pos == end:
            end
        
        grid[pos] = 'visited'
        if 0 < pos < end_of_grid:
            stack.push(pos)

미로찾기

작동 순서
1. 처음 시작 위치를 스택에 push
2. stack이 비어있지 않으면 pop해서 다음에 이동할 위치 설정
3. 현재 위치에서 갈 수 있는 모든 위치를 stack에 push
4. 2, 3 반복

코드

def DFS(start, maze):
    stack = Stack()  # 스택 객체
    stack.push(start) # 출발 위치 삽입 
    # 네 방향 (상, 하, 좌, 우)
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    print("출발", start)
    
    while not stack.isEmpty():  # 스택이 빌 때까지 반복
        position = stack.pop()  # pop 현재 위치 확인
        print("현재 위치", position, end=' -> ')
        x, y = position
        
        if maze[y][x] == 'x':  # 현재 위치가 도착점이면 
            return "탈출 성공"
        
        maze[y][x] = '*'  # 방문 여부를 표시
        for direction in directions:  # 네 방향으로 이동 가능 지점 확인
            next_x, next_y = x + direction[0], y + direction[1]
            if (0 <= next_x < len(maze[0])) and (0 <= next_y < len(maze)) \
                       and maze[next_y][next_x] in ['0', 'x']:
                stack.push((next_x, next_y))  # 이동할 수 있는 지점이면 push
                
        # 스택 출력해 보기
        print("스택", stack.s_list)
        # 미로 출력해 보기
        for row in maze:
            for cell in row:
                print(cell, end=' ')
            print()
        print()
       
    return "탈출 실패"