그래프 : DFS, BFS, 트리, 백트래킹

1. 그래프 이론

그래프는 정점과 간선간의 쌍으로 이루어진 집합입니다.

정점들간의 연결 정보를 나타내는, 즉 그래프를 나타내는 방법은 대표적으로 두 가지가 있습니다. 두 방법 모두 잘 알아두셔야 합니다.

첫 번째 : 인접 행렬 (2차원 배열)

int graph[1000][1000];
(1) 가중치가 없는 그래프
graph[i][j]가 1이면 i번 노드와 j번 노드를 연결하는 간선이 존재한다는 뜻입니다.
(2) 가중치가 있는 그래프
graph[i][j]가 w이면 i번 노드와 j번 노드를 연결하는 간선의 가중치가 w라는 뜻입니다.

그래프가 양방향이면 graph[i][j]와 graph[j][i]의 정보를 같게 해주시면 됩니다.

두 번째 : 인접 리스트 (1차원 배열 x 1차원 가변길이 배열)

(1) 가중치가 없는 그래프
vector<int> G[1000];
G[i]는 i번 노드와 인접한 노드들의 정보를 (순서없이) 담습니다.
담는 방법 : i번째 노드와 j번째 노드가 연결되어있으면
G[i].push_back(j);

(2) 가중치가 있는 그래프
vector<pair<int,int> > G[1000];
G[i]는 i번 노드와 인접한 노드들의 정보와 그 때의 가중치를 같이 담습니다.
담는 방법 : i번째 노드와 j번째 노드가 가중치 w로 연결되어 있으면
G[i].push_back({j, w})

그래프가 양방향이면 G[i].push_back(j)와 G[j].push_back(i)를 둘 다 해주시면 됩니다.

그래프에서 해결할 수 있는 문제는 정말 다양하지만 코테에서는 (1) 그래프 탐색(순회), (2) 그래프의 정점간 경로문제가 주로 나옵니다.

2. DFS

그래프의 탐색 방법에는 대표적으로 두가지가 있습니다. (거의 모든, 어려운 그래프 알고리즘에 기본적으로 나오는 알고리즘입니다) DFS(Depth First Search, 깊이 우선 탐색)와 BFS(Breadth First Search, 너비 우선 탐색)입니다.

DFS는 그래프를 재귀적으로 탐색하는 방법입니다. 즉, 가장 깊은 곳까지 먼저 내려갔다 올라왔다 하는 식입니다.

원래 자료구조로 Stack을 사용하지만, 재귀함수가 stack 특성을 갖고 있어서 편의상 재귀함수를 보통 사용합니다.

visited 배열은 노드의 방문 정보를 나타냅니다. visited배열에는 단순히 방문 정보를 나타낼 수도 있고, 정점 방문 순서를 나타낼 수도 있습니다.