DFS/BFS 개념

스택 자료구조

선입후출 형식
컵에 원소를 한줄로 채워넣는 것으로 이해하면 쉽다.

stack = [] 
stack.append()
stack.pop() : 마지막에 추가한 원소를 제거하면서 동시에 return함. 

큐 자료구조

선입선출 형식
입구와 출구가 뚫려있는 원통으로 이해하면 쉽다.

from collections import deque

queue = deque()
queue.append()
queue.popleft()

재귀함수

자기 자신을 다시 호출하는 함수

사용 시 유의사항

• 종료 조건을 반드시 명시해야 함
• 모든 재귀함수는 반복문을 이용해 동일한 기능을 구현할 수 있음
• 함수를 연속적으로 호출하면, 메모리 내부 스택 프레임에 쌓임.
  그래서 스택 사용해야할 때 라이브러리 대신 재귀함수 사용하는 경우가 많음 !

최대공약수 계산 : 유클리드 호제법

• 유클리드 호제법
  A = B*k + R 일 때, A와 B의 최대공약수는 B와 R의 최대공양수와 같다.

def gcd(a,b):
  if a%b == 0 :
    return b
  else : 
    return gcd(b, a%b) 

"어떤 순서대로 데이터를 탐색할 것인가?"

# 각 노드가 연결된 정보 (2차원 리스트)
graph = [
[], #빈 노드
[2, 3, 8], # 1번 노드는 2,3,8번 노드에 연결됨
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]

# 방문 정보 
visited = [False] * 9 

DFS

• 깊이 우선 탐색
• 스택 or 재귀함수를 이용

수행 과정

1. 탐색 시작 노드를 스택에 삽입 & 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리
   • 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

동작 예시

# DFS 메서드 정의 
def dfs(graph, v, visited) : 
  visited[v] = True  # 현재 노드를 방문 처리 
  print(v, end=' ')
  for i in graph[v] : 
    if not visited[i]:
      dfs(graph, i, vistied)

출력 결과 : 1 2 7 6 8 3 4 5

BFS

• 너비 우선 탐색 : 가까운 노드부터 우선적으로 탐색함
• 큐 이용

수행 과정

1. 탐색 시작 노드를 큐에 삽입 & 방문처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 & 방문처리
3. 더이상 2번 과정을 수행할 수 없을 때까지 반복

동작 예시

from collections import deque 

def bfs(graph, start,visited):
  queue = deque([start])
  visited[start] = True 
  while queue :  # 큐가 빌 때까지 반복 
    v = queue.popleft()
    print(v, end=' ')
	for i in graph[v] :
	  if not visited[i]:
	    queue.append(i)
	    visited[i] = True
        
bfs(graph, 1, visited)    

출력 결과 : 1 2 3 8 7 4 5 6

DFS, BFS 차이는?

• DFS

  • 미로 탐색과 유사하다. 한 방향으로 갈 수 있을 때까지 가다가, 길이 막히면 이전의 갈림길로 돌아와 다시 탐색을 시작한다.
  • 모든 노드를 방문해야할 때 선택한다.
  • BFS보다 구현이 간단하지만, 속도는 느리다.
  • 시간복잡도
    • 인접리스트 : O(N+E)
    • 인접행렬 : O(N^2)

• BFS

  • 두 노드 사이의 최단/임의의 경로를 찾고 싶을 때 사용한다.