[이것이코딩테스트다] DFS/BFS

탐색 알고리즘 (Search)

- 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정, 주로 자료구조 안에서 탐색 하는 문제를 다룸

- 대표적인 탐색 알고리즘

  - DFS(Depth-First-Search)

  - BFS(Breadth-First-Search)

  -> 스택, 큐, 재귀함수, 그래프에 대한 이해 필요

---

자료구조(Data Structure)

- 데이터를 표현하고 관리하고 처리하기 위한 구조

- 자료구조의 기초 개념 : 스택, 큐

-> 두가지 핵심적인 함수로 구성

  - 삽입(Push) : 데이터 삽입

  - 삭제(Pop) : 데이터 삭제

 

+ 오버플로, 언더플로 고민

오버플로 : 특정한 자료구조가 수용할 수 있는 데이터의 크기가 가득 찬 상태에서 삽입할 때 발생

언더플로 : 특정한 자료구조에 데이터가 들어 있지 않은 상태에서 삭제할 때 발생

 

 

 

스택(Stack)

- 박스 쌓기로 생각하면 됨

- 선입후출, 후입선출

 

- 코드 ( 별도의 라이브러리 필요 x )

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

  - pop() : 리스트 가장 뒤의 데이터 꺼내기(삭제)

 

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 최하단 원소부터 출력 -> [5, 2, 3, 1]
print(stack[::-1]) # 최상단 원소부터 출력 -> [1, 3, 2, 5]

 

 

큐(Queue)

- 대기 줄로 생각하면됨

- 선입선출

 

- 코드

  - from collections import deque -> 덱 라이브러리로 큐 구현 가능

  + 덱(Deque)이란? : 스택과 큐의 특징을 모두 가진 자료구조. 양방향으로 데이터 삽입 및 삭제 가능.

  - append() : 가장 뒤에 데이터 삽입

  - popleft() : 가장 앞(왼쪽)의 데이터 꺼내기(삭제)

- 자료형은 list가 아님. 리스트 자료형으로 다룰거면 list(queue)

from collections import deque 

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력 -> deque([3, 7, 1, 4])
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력 -> deque([4, 1, 7, 3])

 

 

 

재귀 함수(Recursive Function)

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

- 함수 정의할 때 그 안에서 함수를 호출

- 무한대로 재귀 호출은 못함. 오류 발생

-> 종료 조건 필요

def recursive_function(i):
    # 3번째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 3:
        return
    print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
    recursive_function(i + 1)
    print(i, '번째 재귀함수를 종료합니다.')

recursive_function(1)

#1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다.
#2 번째 재귀함수에서 3 번째 재귀함수를 호출합니다.
#2 번째 재귀함수를 종료합니다.
#1 번째 재귀함수를 종료합니다.

 

recursive_function(1)

 

- 1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다, recursive_function(2), 1 번째 재귀함수를 종료합니다.

recursive_function(2)

- 2 번째 재귀함수에서 3 번째 재귀함수를 호출합니다, recursive_function(3), 2 번째 재귀함수를 종료합니다.

 

-> recursive_function(1)

: 1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다, 2 번째 재귀함수에서 3 번째 재귀함수를 호출합니다,  2 번째 재귀함수를 종료합니다, 1 번째 재귀함수를 종료합니다.

 

-> 스택 자료구조 같음. 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료(후입선출)

- 재귀함수는 내부적으로 스택 자료구조와 동일

- 스택을 활용하는 상당수 알고리즘은 재귀함수로 간편하게 구현될 수 있음. DFS

 

# 반복적으로 구현한 n!
def factorial_iterative(n):        
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n + 1):
       result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):        
    if n <= 1: # n이 1 이하인 경우 1을 반환
        return 1
    # n! = n * (n - 1)!를 그대로 코드로 작성하기
    return n * factorial_recursive(n - 1)

 

-> 재귀함수가 더 간결. 점화식(재귀식)을 그대로 코드로 옮겼기 때문

점화식 : 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것

팩토리얼 점화식

 

-> n <= 1 인 경우로 종료조건 줘야함.

 

 

그래프(Graph)

- 연결되어 있는 원소 간 관계를 표현한 자료구조

- 노드(Node)와 간선(Edge)로 표현, 노드를 정점(Vertex)라고도 함

- 차수(Degree) : 노드에 연결된 간선의 수

 

- 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것.

- 그래프의 표현 방식 2가지

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

  - 인접 리스트 : 리스트로 그래프의 연결 관계 표현

 

 

인접 행렬

- 파이썬에서는 2차원 리스트로 구현

- 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성 (논리적으로 정답이 될 수 없는 큰 값)

INF = 999999999 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)
print(graph[0][2])

#[[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]
#5

 

 

인접 리스트

- 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장

- 파이썬에서는 2차원 리스트로 구현

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]
#[[],[],[]]

# 노드 0에 연결된 노드 정보 저장 (노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장 (노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보 저장 (노드, 거리)
graph[2].append((0, 5))

print(graph)
#[[(1,7),(2,5)],[(0,7)],[(0,5)]]

 

 

인접 행렬 vs 인접 리스트

---

DFS(Depth-First-Search)

- 깊이 우선 탐색 -> 가장 깊숙이 위치하는 노드에 닿을 때까지 탐색

- 최대한 멀리 있는 노드를 우선으로 탐색

- 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다른 경로로 탐색

- 스택을 이용 -> 재귀 함수로 간결하게 구현 가능

 

동작 과정

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

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

3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복

 

방문처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크

 

DFS 예시 (관행적으로 번호가 낮은 순서부터 처리하도록 구현)

 

시작 노드 1을 스택에 삽입하고 방문 처리

스택의 최상단 노드1에 방문하지 않은 인접 노드(2,3,8) 중에서 가장 작은 노드2를 스택에 넣고 방문 처리

스택의 최상단 노드2에 방문하지 않은 인접 노드7을 스택에 넣고 방문 처리

스택의 최상단 노드7에 방문하지 않은 인접 노드(6,8) 중에서 가장 작은 노드6을 스택에 넣고 방문 처리

스택의 최상단 노드6에 방문하지 않은 인접 노드 없음. 6을 꺼냄. (후입 선출)

스택의 최상단 노드7에 방문하지 않은 인접 노드8을 스택에 넣고 방문 처리

스택의 최상단 노드8에 방문하지 않은 인접 노드 없음. 8을 꺼냄.

스택의 최상단 노드7에 방문하지 않은 인접 노드 없음. 7을 꺼냄.

스택의 최상단 노드2에 방문하지 않은 인접 노드 없음. 2를 꺼냄.

스택의 최상단 노드1에 방문하지 않은 인접 노드3을 스택에 넣고 방문 처리

스택의 최상단 노드3에 방문하지 않은 인접 노드(4,5) 중에서 가장 작은 노드4를 스택에 넣고 방문 처리

스택의 최상단 노드4에 방문하지 않은 인접 노드5를 스택에 넣고 방문 처리

남아 있는 노드에 방문하지 않은 인접 노드가 없음. 모든 노드를 차례대로 꺼냄

 

노드 탐색 순서(스택에 삽입한 순서)

: 1-2-7-6-8-3-4-5

 

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
# 빈 리스트를 0번 노드로 가정하고 만들어두는게 코드 간단
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited) # 1 2 7 6 8 3 4 5

 

 

 

BFS(Breadth-First-Search)

- 너비 우선 탐색 -> 가까운 노드부터 탐색

- 큐를 이용 -> 인접한 노드를 반복적으로 큐에 넣도록 알고리즘 작성

 

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

BFS 예시

 

시작 노드 1을 큐에 삽입하고 방문 처리

[1]

큐에서 노드1을 꺼내고(선입선출) 방문하지 않은 인접 노드(2,3,8)를 모두 큐에 삽입하고 방문 처리

[2,3,8]

큐에서 노드2를 꺼내고 방문하지 않은 인접 노드7을 큐에 삽입하고 방문 처리

[3,8,7]

큐에서 노드3을 꺼내고 방문하지 않은 인접 노드(4,5)를 큐에 삽입하고 방문 처리

[8,7,4,5]

큐에서 노드8을 꺼내고 방문하지 않은 인접 노드가 없어서 무시

[7,4,5]

큐에서 노드7을 꺼내고 방문하지 않은 인접 노드6을 큐에 삽입하고 방문 처리

[4,5,6]

남아 있는 노드에 방문하지 않은 인접 노드가 없음. 모든 노드를 차례대로 꺼냄

[5,6]

[6]

[]

노드 탐색 순서(큐에 삽입한 순서)

: 1-2-3-8-7-4-5-6

 

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8], # 1과 연결된 노드들
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 # 하나 더 큰 크기로

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

 

 

 

배열도 그래프 형태로 생각해서 풀어라!

 

다음과 같이 3x3 형태의 좌표를 우측 그래프 형태로 바꿔서 생각 

코테에서 탐색 문제 만나면 그래프 형태로 표현하고 풀이법 생각

 

 

DFS vs BFS

- 시간 복잡도는 둘다 O(N) 으로 같지만, 실제 수행시간은 BFS가 DFS보다 조금 더 좋은편