그래프
그래프 정의
수학(그래프이론)에서 그래프란, 객체 일부 쌍(pair)들이 '연관되어' 있는 객체 집합 구조를 말한다.
그래프라 하면 일반적으로 '정점(노드)'과 '간선(엣지)'으로 이루어진 자료구조를 의미한다.
또한 간선의 방향 유무에 따라서 단방향 그래프와 무방향 그래프(또는 양방향)로 나뉜다.
그래프 표현
그래프를 표현하는 방법은 크게 인접 행렬 그래프와 인접 리스트 그래프의 두가지 방법이 있다.
1. 인접 행렬 그래프
모든 노드의 간선의 정보를 저장한다.
- 장점: 직관적이며 쉽게 구현 가능
- 단점: 불필요한 정보의 저장이 많으며, 그래프의 크기가 커지면 메모리 초과가 발생할 수 있음
- 구현: int형의 2차원 배열을 주로 이용하며, 이동할 수 있으면 1, 없으면 0으로 표기함
2. 인접 리스트 그래프
- 장점: 필요한 정보만 저장하여 메모리 절약 가능
- 단점: 인접행렬에 비해 다소 어려움
- 구현: 리스트(List)나 벡터(Vector)등의 자료구조를 이용하여 각 정점에서 이동가능한 정점들을 저장
- 무(양)방향 그래프
그래프 탐색
그래프의 각 정점을 방문하는 그래프 탐색(Graph Traversals)은 아래와 같이 깊이 우선 탐색(Depth-First Search, DFS), 너비 우선 탐색(Breadth-First Search, BFS), 다익스트라, 플로이드 와샬 등 크게 4가지 방법이 있다.
1. DFS
DFS(깊이 우선 탐색)는 19세기 프랑스의 수학자 찰스 피에르 트레모가 고안한 것으로 알려져 있으며,
일반적으로 BFS에 비해 널리 쓰인다.
(코딩테스트 시에도 대부분의 탐색은 DFS로 구현함.)
현재 정점(노드)에서 연결된 정점(노드) 하나를 골라 깊이 끝까지 탐색을 진행하여 끝까지 진행한 경우 백트래킹을 하여 다음 노드로 탐색을 진행해
아래와 예시와 같이 탐색을 한다.
DFS는 주로 스택을 통한 반복이나 재귀를 통한 반복 구조로 구현하며,
백트래킹을 통해 뛰어난 효용을 보인다.
백트래킹(Backtracking)
백트래킹은 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다는 데서 유래했다.
해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙)해 정답을 찾아가는 범용적인 알고리즘으로 주로 재귀로 구현하여 모두 DFS의 범주에 속한다.
재귀는 반복되는 조건과, 종료 조건을 통해 구현하는데 이때의 종료 조건을 설정하여 재귀 호출된 함수가 종료 조건을 만족하여 탐색을 하지 않고 return 되는 것이 백트래킹이다.
제약 충족 문제(Constraint Satisfaction Problems, CSP)에 특히 유용하다.
2. BFS
BFS(Breadth First Search; 너비 우선 탐색)는 현재 정점과 연결된 정점들에 대해 우선적으로 넓게 탐색하는 방식이다.
최단 경로를 찾는 다익스트라 알고리즘 등에 매우 유용하게 쓰이며 큐를 통한 반복 구조로 구현하며 재귀로는 구현이 불가하다.
Reference)
파이썬 알고리즘 인터뷰
https://m.blog.naver.com/occidere/220923695595 - 그래프
1차 작성 - 22.08.22
-> 다익스트라, 플로이드 웨셜 정리 필요
