[코테] DFS/BFS 공부하기

Day8

탐색(Search) : 많은 데이터 중에서 원하는 데이터를 찾는 과정

DFS/BFS는 대표적인 탐색 알고리즘. 스택 & 큐에 대한 이해가 필요.

 

자료구조(Data Structure) : 데이터를 표현, 관리, 처리하기 위한 구조

- push : 데이터 삽입

- pop : 데이터 삭제

- overflow : 수용 가능한 데이터의 크기를 넘은 상태에서 삽입 연산 수행 시 발생

- underflow : 자료구조에 데이터가 없는데 삭제 연산 수행 시 발생

 

스택(Stack) : FILO(First In Last Out). 선입후출. LIFO(Last In First Out). 후입선출.

=> 먼저 쌓은 것은 나중에 뺄 수 있고, 나중에 쌓은 것은 먼저 뺄 수 있음.

- append() : 리스트 맨 뒤에 데이터 삽입

- pop() : 리스트 맨 뒤 데이터 삭제

 

큐(Queue) : FIFO(First In First Out). 선입선출.

=> 먼저 들어오면, 먼저 나갈 수 있음. 공정한 자료구조. 

from collections import deque

queue = deque() # 큐 구현을 위한 deque 라이브러리

queue.append(4) # 4추가
queue.append(5) # 5추가
queue.append(3) # 3추가
queue.popleft() # 4삭제

print(queue) # 큐 출력(앞부터) # deque([5, 3])
queue.reverse() # 앞 뒤 전환
print(queue) # 큐 출력(뒤부터) # deque([3, 5])
print(list(queue)) # [3, 5]

 

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

def re_fun():
  print("호출")
  re_fun()
  
re_fun() # "호출"이라는 단어를 무한히 출력

ex) 팩토리얼

def factorial1(n):
  result = 1
  for i in range(1, n+1):
    result *= i
  return result

print(factorial1(5))

def factorial2(n):
  if n <= 1:
    return 1
  return n * factorial2(n-1)
print(factorial2(5))

factorial1로 값을 구할 때와 factorial2로 값을 구할 때는 모두 120으로 같은 결과를 얻을 수 있다.

그런데 factorial2와 같이 재귀함수로 코딩하면 점화식을 활용하여 더 간결하게 코딩할 수 있다.

 

---

 

DFS(Depth First Search) : 깊이 우선 탐색. 그래프 깊은 부분부터 우선적으로 탐색하는 알고리즘.

스택 자료구조 이용. 재귀함수 이용해서 구현.

* 그래프 - 노드(node; 정점vertex) & 간선(edge)으로 표현

- 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현한는 방식

- 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

def dfs(graph, v, visited):
  visited[v] = True # 현재 노드 방문 처리
  print(v, end=' ')
  # 해당 원소와 연결된 다른 노드 재귀적 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)
      
graph = [
  [],
  [2, 3, 8],
  [1,7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1,7]
]

visited = [False] * 9
bfs(graph, 1, visited) # 1 2 7 6 8 3 4 5

 

 

BFS(Breadth First Search) : 너비 우선 탐색. 가까운 노드부터 탐색하는 알고리즘.

큐 자료구조를 이용해서 먼저 들어온 것이 먼저 나가도록 가까운 노트부터 탐색을 진행. - deque

from collections import deque

def bfs(graph, start, visited):
queue = dequeue([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
      
graph = [
  [],
  [2, 3, 8],
  [1,7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1,7]
]

visited = [False] * 9
bfs(graph, 1, visited) # 1 2 3 8 7 4 5 6