그래프 (graph)

- 구성요소

• 정점 Vertex (=node)
• 간선 Edge

- 분류기준

• 방향성
• 순환성 (사이클)

- DAG

(Directed Acyclic Graph)

• 방향성 비순환 그래프
• ex) git에서 브랜치, 블록체인(암호화폐 등)에서 사용됨

트리 (tree)

- 인접행렬로 구현

인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식

• 간선(E) 개수가 많을수록 유리하다. (밀집그래프)
• 장점 : 탐색이 빠름
• $O(V^2)$
• 주의 : 그래프의 요소들을 map에 좌표로 찍어 탐색하는 문제는 인접행렬이라고 볼 수 없다. 이 경우 시간복잡도도 달라지므로 유의하자.
  (참고 1743 음식물 피하기)
  

- 인접리스트로 구현

• 간선(E) 개수가 적을수록 유리하다. (희소그래프)
• 연결리스트로 구현해도 되지만, 편하게 동적 배열 (vector)로 구현하는 경우도 많음
• 장점 : 메모리를 적게 씀
• $O(V+E)$

DFS

• 깊이 우선 탐색
• 스택 or 재귀로 구현

BFS

• 너비 우선 탐색
• 큐로 구현

최단거리

DFS와 BFS의 차이는 최단거리를 구하는 문제에서 드러난다.
DFS는 모든 경로를 가봐야 하지만 BFS는 탐색 과정에서 찾고자 하는 도착 노드를 최초로 찾았다면 그것이 최단거리임이 보장이 되므로

• BFS가 더 유리하다.

길찾기

• DFS, BFS 모두 가능 (편한거 사용)

백트래킹 (Backtracking)

• 백트래킹도 기본적으로 모든 경우를 탐색하는 완전 탐색이며 DFS나 BFS 방식으로 구현한다

• 하지만 백트래킹은 가지치기를 통해 탐색 경우의 수를 줄인다는 차이가 있다

• 최악의 경우, 모든 경우를 다 살펴보게 될 수도 있지만 가능한 덜 보겠다는 전략

1. 어떤 노드의 유망성을 점검 후, 유망하지 않으면 배제시킨다. = 가지치기
2. 해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. → 풀이시간 단축

백트래킹의 시간 복잡도는 가지치기를 하나도 못했을 경우, 즉 최악의 경우를 생각해야한다. 따라서 가지가 2개일 경우에 시간 복잡도는 $O(2^N)$ 이다.