[Python] 그래프 탐색 알고리즘: DFS/BFS _ 스택 자료구조

• 탐색(Search)이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다.
• 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있습니다.
• DFS와 BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 합니다.

스택 자료구조

• 먼저 들어온 데이터나 나중에 나가는 형식(선입후출)의 자료구조입니다.
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있습니다.

 

스텍 구현 예제

stack = [ ]     #리스트 자료형 사용한다.

#삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제( ) - 삽입(1) - 삽입(4) - 삭제( )
stack.append(5)     #가장 오른쪽에 원소 삽입 : append()
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop( )          #가장 오른쪽에서 원소 꺼낸다 : pop()
stack.append(1)
stack.append(4)
stack.pop( )
 
print(stack[ ::-1 ])     #최상단 원소부터 출력 = 먼저 나가고자 하는 원소
print(stack)     #최하단 원소부터 출력

 

(실행결과)
[ 1, 3, 2, 5 ]
[ 5, 2, 3, 1 ]

• 파이썬에서 리스트를 사용해서 스택을 구현할 수 있ㅅ다.