그래프 순회 Graph Traversals
순회를 위한 그래프 준비
깊이 우선 탐색(Depth First Search : DFS)
- 재귀 구현
  - 수도코드
  - Python 구현
- 스택 구현
백트래킹 Backtracking
- 제약 충족 문제 Constraint Satisfaction Problems
넓이 우선 탐색(Breadth-First Search : BFS)

그래프 순회 Graph Traversals

그래프 순회: 그래프 탐색 Search 이라고도 불리우며 그래프의 각 정점을 방문 하는 과정을 말한다.

DFS: 깊이 우선 탐색 Depth First Search
BFS: 너비 우선 탐색 Breadth-First Search의 2가지 알고리즘이 있음

순회를 위한 그래프 준비

파이썬의 딕셔너리 자료형으로 구현

키: 출발 노드
값: 도착 노드

graph = { 
 A: [B, C, D], 
 B: [E], 
 C: [E], 
 D: [], 
 E: [F, G], 
 F: [], 
 G: [C]
 } 

모든 정점들을 방문한 후 탐색을 종료함
순차적인 프로그램보다는 DFS 알고리즘을 재귀(recursive) 알고리즘으로 구현하는 것이 좋음
재귀 알고리즘으로 구현할 경우에는 스택(stack)을 사용함

깊이 우선 탐색(Depth First Search : DFS)

맹목적 탐색 기법 중 하나로, 자식 노드를 확장할 수 있을 때까지 깊이 우선으로 탐색을 진행하는 방법
일반적으로 BFS에 비해 더 널리 쓰임
코딩 테스트 시에도 대부분의 그래프 탐색은 DFS로 구현하게 될 것임

주로 스택으로 구현하거나 재귀로 구현
- 일반적으로 DFS는 스택으로 구현
- 재귀를 이용하면 좀더 간단하게 구현 가능(코테 시 더 많이 쓰임)
이후에 살펴볼 백트래킹을 통해 뛰어난 효용을 보임

재귀 구현

수도코드

DFS(G, v) 
 label v as discovered 
 for all directed edges from v to w that are in G.adjacentEdges(v) do 
  if vertex w is not labeled as discovered then 
   recursively call DFS(G, w)

(해석)

정점 v 의 모든 인접 유향 Directed 간선들을 반복하라고 표기됨

Python 구현

def recursive_dfs(v, discovered=[]):
 # 방문한 노드 기록
 discovered.append(v) 
 for w in graph[v]:
  #  현재 방문한 노드와 연결되어 있는 노드 (w)
  if w not in discovered:
   # w가 방문되지 않았을 경우에 아래 실행
   discovered = recursive_dfs(w, discovered) 
  return discovered

[탐색 결과]

>>> f'recursive dfs: {recursive_dfs(1)}'
'recursive dfs: [A, B, E, F, G, C, D]'

스택 구현

수도코드

DFS-iterative(G, v) 
    let S be a stack 
    S.push(v) 
    while S is not empty do 
        v = S.pop() 
        if v is not labeled as discovered then 
            label v as discovered 
            for all edges from v to w in G.adjacentEdges(v) do
                S.push(w)

Python

def iterative_dfs(start_v):
    discovered = [] 
    stack = [start_v] 
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v) 
            for w in graph[v]:
                stack.append(w) 
        return discovered

[탐색 결과]

>>> f'iterative dfs: {iterative_dfs(1)}'
'iterative dfs: [A,D,C,E,G,F,B]'

평가

앞서 코드가 길고 빈틈없어 보이는 재귀 구현에 비해 우아함은 떨어지지만
좀 더 직관적 -> 이해하기는 훨씬 더 쉬움
실행 속도 또한 더 빠른 편

대부분의 경우 재귀 구현과 반복구현 동시구현 가능

서로 바꿔서 알고리즘을 구현할 자유롭게 바꿔가며 익숙해질 때까지 꾸준히 연습 필요

[똑같은 DFS인데 순서가 다른 이유]

재귀 DFS: 사전식 순서 Lexicographical Order로 방문
반복 DFS는 역순으로 방문
스택으로 구현: 가장 마지막에 삽입된 노드부터 꺼내서 반복해서

백트래킹 Backtracking

해결책에 대한 후보를 구축해 나아가다 가능성이 없는 후보를 포기(백트랙 Backtrack )해 정답을 찾아가는 범용적인 알고리즘

탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다는데서 유래

가보고 되돌아오고를 반복: 운이 좋으면 시행착오를 덜 거치고 목적지에 도착할 수 있지만 최악의 경우에는 모든 경우를 다거친 다음에 도착할 수 있다.

주로 재귀로 구현

제약 충족 문제 Constraint Satisfaction Problems 에 특히 유용

DFS(깊이 우선 탐색)를 이야기하다 보면 항상 백트래킹이라는 단어가 함께 나옴

백트래킹은 DFS보다 좀 더 광의의 의미를 지님.
백트래킹은 DFS와 같은 방식 으로 탐색하는 모든 방법을 뜻하며, DFS는 백트래킹의 골격을 이루는 알고리즘.

탐색해야 하는 가지가 많은 트리

브루트 포스로 전체 트리를 탐색한다면
매우 긴 시간이 소요
트리의 가지치기 Pruning 이용
하지만 그림 12-10과 같이 DFS로 탐색을 시도하면
가능성이 없는 후보는 즉시 포기하고 백트래킹
트리의 불필요한 거의 대부분을 버릴 수 있음

제약 충족 문제

= Constraint Satisfaction Problems
이하 CSP
백트래킹이 필수적.
제약 충족 문제: 수많은 제약 조건 Constraints 을 충족하는 상태 States 를 찾아내는 수학 문제

넓이 우선 탐색(Breadth-First Search : BFS)

그래프의 최단 경로를 구하는 문제 등에 사용됨

주로 큐로 구현

너비 우선 탐색
DFS보다 쓰임새는 적음
최단 경로를 찾는 다익스트라 알고리즘 등에 매우 유용하게 쓰임

큐 구현

수도코드

스택을 이용하는 DFS와 달리, BFS를 반복 구조로 구현할 때는 큐를 이용

BFS(G, start_v) 
 let Q be a queue 
 label start_v as discovered 
 Q.enqueue(start_v) 
 while Q is not empty do 
  v := Q.dequeue() 
  if v is the goal then 
   return v 
  for all edges from v to w in G.adjacentEdges(v) do
   if w is not labeled as discovered then 
    label w as discovered 
    w.parent := v 
    Q.enqueue(w)

Python 구현

def iterative_bfs(start_v):
 discovered = [start_v] 
 queue = [start_v]
 while queue:
  v = queue.pop(0) 
  for w in graph[v]:
   if w not in discovered:
    discovered.append(w) 
    queue.append(w) 
  return discovered

[탐색 결과]

>>> f'iterative bfs: {iterative_bfs(1)}'
'iterative bfs: [A,B,C,D,E,F,G]'

결과

리스트 자료형을 사용했지만 pop(0) 과 같은 큐의 연산만을 사용.
따라서 큐를 사용 하는 것과 사실상 동일
좀 더 최적화를 위해서는 데크 같은 자료형을 사용해 보는 것을 고민 가능

BFS의 장점

노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름
3 .너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다.

BFS의 단점

재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다.

재귀 구현 불가

이번에는 BFS를 재귀로 풀이해볼 수 있을까?
사실 많은 이가 혼동하는 부분인데 BFS는 재귀로 동작하지 않음
큐를 이용하는 반복 구현만 가능

Coding test

[020] Concept(비선형자료구조_깊이 우선 탐색:DFS/넓이 우선 탐색: BFS)

16 Feb 2020

목차

그래프 순회 Graph Traversals

순회를 위한 그래프 준비

깊이 우선 탐색(Depth First Search : DFS)

재귀 구현

수도코드

Python 구현

스택 구현

수도코드

Python

평가

백트래킹 Backtracking

제약 충족 문제

넓이 우선 탐색(Breadth-First Search : BFS)

큐 구현

수도코드

Python 구현

결과

BFS의 장점

BFS의 단점

재귀 구현 불가