[Do it! 알고리즘 코딩테스트 with C++] 6장. 그래프

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 목차 - 6장. 그래프

6-1. 유니온 파인드
6-2. 위상정렬
6-3. 다익스트라
6-4. 벨만-포드
6-5. 플로이드-워셜
6-6. 최소 신장 트리

---

📌 6-1. 유니온 파인드

* 유니온 파인드
- 그래프 내의 임의 두 노드가 서로 연결되어있는지 판별하기위해 사용되는 부분 알고리즘

* 유니온 파인드 용어
- union 연산: 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶음
- find 연산: 두 노드가 같은 집합에 속해 있는지를 확인, 자신의 대표 노드를 찾아준다.

* 유니온 파인드 동작 원리
1. 대표 노드 저장 배열에 각 노드를 초기화
2. 유니온 연산 - 대표 노드끼리 연결해준다.
3. 파인드 연산 - 해당 노드의 대표 노드로 이동한 후 값이 같은지 비교한다.

* 파인드 연산
1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인한다.
2. 동일하지 않으면 value값이 가리키는 index 위치로 이동한다.
3. 이동 위치의 index 값과 value 값이 같을 때까지 1~2를 반복한다. (재귀함수로 구현)
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경한다. (경로 압축 - 시간복잡도 최적화)

---

📌 6-2. 위상정렬

* 위상 정렬
- 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
- 기능: 노드 간의 순서를 결정
- 특징: 사이클이 없어야 함
- 시간 복잡도: O(V+E)

* 위상 정렬 용어
- 진입차수: 자기 자신을 가리키는 에지의 개수

* 위상 정렬 동작 원리
1. 진입 차수 배열 초기화 - 인접 리스트를 통해서 진입차수 계산
2. 진입 차수가 0인 미방문 노드 선택 -> 위상 정렬 배열에 추가, 인접 노드의 진입 차수 업데이트(-1)

---

📌 6-3. 다익스트라

* 다익스트라
- 그래프에서 최단 거리를 구하는 알고리즘
- 기능: 특정 출발 노드와 모든 노드 간의 최단 거리 탐색
- 특징: 에지는 모두 양수
- 시간 복잡도: O(ElogV)

* 다익스트라 동작 원리
1. 인접 리스트로 그래프 구현
2. 최단 거리 배열 초기화 - 출발 노드가 0, 나머지는 무한
3. 최단 거리 배열에서 값이 가장 작은 미방문 노드 선택
4. 해당 노드의 인접 노드들의 최단 거리값 업데이트 - min(해당노드 최단거리값+가중치, 인접노드 최단거리값)

---

📌 6-4. 벨만-포드

* 벨만-포드
- 그래프에서 최단 거리를 구하는 알고리즘
- 기능: 특정 출발 노드와 모든 노드 간의 최단 거리 탐색
- 특징: 음수 가중치 에지가 있어도 수행 가능, 음수 사이클의 존재 여부 판단 가능
- 시간 복잡도: O(VE)

* 벨만-포드 동작 원리
1. 에지 리스트로 그래프 구현
2. 최단 거리 배열 초기화 - 출발 노드가 0, 나머지는 무한
3. 모든 에지를 확인 후 최단 거리 배열 업데이트 - 출발 노드가 무한이 아닌 에지만 확인한다.
4. 3번을 (노드 총 개수 - 1)만큼 반복
5. 마지막 한 번 더 반복해서 음수 사이클 유무 확인

* 음수 사이클 유무 확인하기
- 마지막 N번 째 반복했을 때 배열의 업데이트가 일어나면 해당 그래프는 최단 거리를 구할 수 없는 그래프다. = 음수 사이클이 존재한다.

---

📌 6-5. 플로이드-워셜

* 플로이드-워셜
- 그래프에서 최단 거리를 구하는 알고리즘
- 기능: 모든 노드 간의 최단 거리 탐색
- 특징: 음수 가중치 에지가 있어도 수행 가능, 동적 계획법의 원리를 이용해 알고리즘에 접근
- 시간 복잡도: O(V^3)

* 플로이드-워셜 동작 원리
- 전체의 최단 경로는 각 부분(한 노드부터 다른 노드까지)의 최단경로가 연결된 형태다.
- 노드의 수가 많지 않기 때문에 최단 거리(출발->도착까지) 행렬을 만들 수 있다.
1. 최단 거리 행렬 초기화 - 자기 자신(Start == End)은 0,  나머지는 무한
2. 최단 거리 행렬에 그래프 데이터 저장
3. 점화식으로 행렬 업데이트 - 3중 for문의 형태 // 경유지 K (1~N), 출발 S (1~N), 도착 E (1~N)

* 점화식
- D[S][E] = min(D[S][E], D[S][K] + D[K][E])

---

📌 6-6. 최소 신장 트리

* 최소 신장 트리 
- 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리
- *크루스칼, 프림 알고리즘 사용
- 특징: 사이클은 가중치의 합이 최소가 될 수 없으므로 포함하지 않는다. 최소 신장 트리 구성 에지는 항상 N - 1개다.

* 최소 신장 트리 동작 원리
1. 에지 리스트로 그래프 구현 & 유니온 파인드 리스트 초기화 - 유니온 파인드를 통해 사이클 판별하기 위함
2. 에지 리스트를 가중치 오름차순으로 정렬
3. 가중치가 낮은 에지부터 연결 시도 - 파인드 연산을 통해 서로 다른 집합임을 판별했을 때(루트노드가 서로 다름)만 연결
4. N-1개의 에지가 연결될 때까지 3번 반복 -> 연결된 에지 개수 & 비용 합 카운트
5. 총 에지 비용 출력

---