그래프 탐색 알고리즘 : DFS,BFS

• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말함.
• 대표적인 그래프 탐색 알고리즘으로 DFS,BFS가 있음.
• DFS,BFS를 공부하기에 앞서 알아야할 자료구조를 공부해야 한다.

스택(stack) 자료구조

• 먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조
• 입구와 출구가 동일한 형태
• 박스에 물건을 넣고 꺼낼때를 생각해보면 된다.

python 스택 구현

x = []

x.append(1)
x.append(2)
x.append(3)
x.pop()
x.append(4)
x.pop()
x.append(5)

print(x) # 최하단 원소 순서대로 출력 
print(x[::-1]) # 최상단 원소 순서대로 출력 

출력 결과 : 
[1,2,5]
[5,2,1] 

큐 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식의 자료구조
• 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 생각하면 이해하기 쉬움

python 큐 구현

form collections import deque
# 큐 구현을 위해서 deque 라이브러리 사용
queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)
queue.popleft() # 왼쪽 원소 꺼내기 
queue.append(4)
queue.append(5)
queue.popleft() 

print(queue) # 먼저 들어온 원소부터 출력
queue.reverse() # 뒤집기 
print(queue) # 나중에 들어온 원소부터 출력

• python에서 큐를 구현할 때 리스트 자료형을 이용하는것보다 deque를 이용하는것이 시간적으로 유리하다.

  재귀 함수

• 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미

• 재귀 함수를 무한히 출력하게 되면 최대 재귀 깊이 초과 메세지가 출력 되면서 프로그램이 종료 됩니다. 무한히 출력 되는 재귀 함수를 만들면

  def recuseive():
      print("재귀 함수를 호출합니다.")
      recursive()
  
  print(recursive())
  
  출력결과 : 
  재귀 함수 호출
  재귀 함수 호출
  재귀 함수 호출
  .
  .
  .
  Traceback (most recent call last):

위의 코드를 보면 재귀 함수가 계속 호출되다가 최대 재귀 깊이를 초과해 메세지가 출력되는것을 확인할 수 있습니다.

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 조건을 명시하지 않으면 함수가 무한히 호출될 수 있음.
• 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많습니다.

DFS (Depth-First Search)

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다.
• DFS는 스택 자료구조나 재귀함수를 이용하여 문제를 해결합니다. 그 과정은
  1. 탐색 시작 노드를 스택에 삽입 후 방문처리
  2. 스택에 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  3. 위의 과정을 꺼낼 노드가 없을때까지 반복

BF(Breadth-First Search)

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 입니다.
• BFS는 큐 자료구조를 이용하고 동작 과정을 설명하자면
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드와 인접한 노드 중에 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리
  3. 2번 과정을 반복하지 못하면 종료
• 최단경로 문제에 많이 사용