하기 내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬(저자: 나동빈님)'의 책을 정리한 내용입니다.

chap05. DFS/BFS

• 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

• 오버플로 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산 수행 시 발생
• 언더플로 : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산 수행 시 발생

• 스택 : 선입후출(LIFO)
• 큐 : 선입선출(FIFO)

Deque(덱)

스택과 큐의 장점을 모두 채택한 것
데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적
queue 라이브러리 이용하는 것보다 더 간단
→ 대부분의 코딩 테스트에서 collections 모듈과 같은 기본 라이브러리 사용 허용

재귀함수

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

• 무한대로 재귀 호출을 진행할 수 없음
  컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조 이용)
  → 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료됨

DFS(Depth First Search)

깊이 우선 탐색 → 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

• 후입선출 - 스택 사용
  • 노드(정점)
  • 간선
• 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

  • 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

    INF = 999999
    
    graph = [
    	[0, 7, 5],
    	[7, 0, INF],
    	[5, INF, 0]
    ]

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

  • 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해 저장

    graph = [[] for _ in range(3)]
    
    graph[0].append((1, 7))
    graph[0].append((2, 5))
    
    graph[1].append((0, 7))
    
    graph[2].append((0, 5))

• 인접 행렬 : 모든 관계를 저장

  • 노드 개수가 많을수록 메모리가 불필요하게 낭비됨

• 인접 리스트 : 연결된 정보만을 저장

  • 메모리를 효율적으로 사용
  • 인접행렬에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림
  • 연결된 데이터를 하나씩 확인해야 하므로

• DFS의 동작 방식

  1. 탐색 시작 노드를 스택에 삽입하고 방문처리

  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리

     방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드 꺼냄

  3. 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 = [
       [], [], ...
     ]
     
     visited = [False] * 9
     dfs(graph, 1, visited)

BFS(Breath First Search)

너비 우선 탐색 → 가까운 노드부터 탐색하는 알고리즘

↔ DFS : 최대한 멀리 있는 노드를 우선으로 탐색하는 방식

• 선입선출 - 큐 사용

• BFS의 동작 방식

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

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

2차원 배열에서의 탐색 문제를 만날 경우 → 그래프 형태로 바꿔서 생각하면 방법을 쉽게 떠올릴 수 있음

코딩 테스트에서 탐색 문제를 볼 경우 → 그래프 형태로 표현한 다음 풀이법 고민