(이코테 w/ Python) DFS & BFS - 스택과 큐
그래프 탐색 알고리즘: DFS/BFS
탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
특정 조건에 맞는 데이터가 존재하는지, 존재한다면 어떤 위치에 존재하는지 등을 찾고자 하는 목적으로 다양한 탐색 알고리즘을 사용한다.
대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.
코딩 테스트에서 매우 자주 등장하는 유형이다 (⭐️⭐️⭐️⭐️⭐️ 반드시 숙지하도록)
스택 자료구조
먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.
입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
예를 들어, 여러 개의 박스를 쌓을 때 (스택하고자 할 때) 아래쪽에서부터 차례대로 박스를 올려놓는다.
쌓아 올린 박스를 다시 내려놓고자 할 때는 가장 위쪽에 있는 박스부터 차례대로 내린다.
스택 동작 예시
7까지 데이터를 입력하여 삽입한다. 삽입한 순서대로 데이터가 쌓였다.
여기서 데이터를 삭제한다면 제일 나중에 삽입한 7이 삭제된다.
7 삭제 후 1과 4를 삽입하여 5개의 데이터를 쌓는다.
이후 한번 더 삭제를 하게되면 제일 나중에 삽입된 4가 삭제된다.
파이썬에서 스택 자료구조 유형을 사용하기 위해서는 리스트 자료형을 사용하면 된다.
리스트 자료형은 가장 오른쪽에 원소를 삽입하는 append method와 원소를 꺼내는 pop method를 지원하기 때문에 이를 그대로 스택과 같이 사용한다.
append(), pop()의 시간 복잡도는 상수시간 (O(1))이기 때문에 스택에 사용되기 적합하다.
그래서 별도의 라이브러리를 사용할 필요없다.
큐 자료구조
먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.
큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있다.
데이터가 왼쪽에서 들어와 오른쪽으로 나가는 것을 표현하였다.
5, 2, 3, 7이 차례대로 들어와 왼쪽부터 7, 3, 2, 5로 데이터가 쌓인 것을 확인할 수 있다.
제일 먼저 들어온 데이터(5)가 오른쪽에 위치하고 제일 나중에 들어온 데이터(7)가 왼쪽에 위치한다.
여기서 데이터를 삭제하게 되면 제일 먼저 들어온 5가 삭제된다.
이후 다시 데이터를 삽입한다면 제일 왼쪽에 1이 들어와 있는 것을 확인할 수 있다.
덱(deque) 라이브러리를 사용한다.
리스트 자료형을 이용해서 큐를 구현할 수 있지만 리스트 자료형을 이용하는 경우 기능적으로는 가능하지만 시간 복잡도가 더 높기 때문에 비효율적이다.
queue = deque(): 하나의 덱 객체를 생성한 뒤에
원소 삽입 시 append(), 삭제 시 popleft() 함수를 이용한다.
덱 라이브러리는 스택과 큐 자료구조에 장점을 모두 합친 자료구조이다.
덱 라이브러리에 원소를 삽입할 때 append() 함수는 리스트에서의 append()와 동일하게 동작한다.