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

• 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다

• DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형

• 스택 자료구조

  • 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
  • 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
  • 리스트 자료형 사용 (stack = [])
  • 삽입(append()) / 삭제(pop())로 구성

• 큐 자료구조

  • 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
  • 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화
  • 라이브러리 사용(from collections import deque)
  • 삽입(append()) / 삭제(popleft())

• 재귀 함수

  • 자기 자신을 다시 호출하는 함수
  • 재귀 함수 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 된다.

• DFS(Depth-First Search)

  • DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
  • 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

  INF = 999999999
  
  graph = [
  	[0, 7, 5],
  	[7, 0, INF],
  	[5, INF, 0]
  ]
  
  print(graph)
  [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]
  

  • 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

  
  # 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
  graph = [[] for _ in range(3)]
  
  # 노드 0에 연결된 노드 정보 저장(노드, 거리)
  graph[0].append((1, 7))
  graph[0].append((2, 5))
  
  graph[1].append((0, 7))
  
  graph[2].append((0, 5))
  
  print(graph)
  [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]
  

  • DFS는 스택 자료구조(혹은 재귀 함수)를 이용
    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
    2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
    3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

• BFS(Breadth-First Search)

  • BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
  • BFS는 큐 자료구조를 이용한다
    1. 탐색 시작 노드를 큐에 삽입하고 방문 처리함
    2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
    3. 더 이상 2번의 과정을 수행할 없을 떄까지 반복

예시

Coding_Test_Study/삼성준비/DFS+BFS at main · jaesukpark77/Coding_Test_Study