[알고리즘/코딩테스트👩‍💻] Do it! 알고리즘 코딩테스트 C++ 8장 그래프

교재 : Do it! 알고리즘 코딩테스트 c++ (김종관, 이지스퍼블리싱)
공부 깃허브 : https://github.com/yeonjae02/algorithmStudy_cpp

GitHub - yeonjae02/algorithmStudy_cpp: Do it! 알고리즘 코딩테스트 C++ 을 공부하며 작성한 코드 저장소

---

8.1 그래프의 표현

1) 에지 리스트 (edge list)

- 에지를 중심으로 그래프를 표현한다.
- 배열에 출발 노드, 도착 노드, (가중치)를 저장하여 에지를 표현한다.
- 구현이 쉬우나 특정 노드와 곤련된 에지를 탐색하기 어렵다.
- 노드 사이의 최단 거리를 구하는 벨만-포드, 최소 신장 트리를 찾는크루스칼 알고리즘에 사용한다.
- 노드 중심 알고리즘에는 잘 사용하지 않는다.
 

2) 인접 행렬 (adjacency matrix)

- 2차원 배열을 자료구조로 활용하여 그래프를 표현한다.
- 노드 중심으로 그래프를 표현한다.
- 그래프 구현이 쉽다.
- 두 노드를 연결한 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있다.
- 노드와 관련된 에지를 탐색하려면 n번 접근해야 하므로 시간 복잡도가 인접 리스트에 비해 느리고 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다. 
 

3) 인접 리스트 (adjacency list)

- 이차원 벡터로 그래프를 표현한다.
- 그래프 구현이 복잡하다.
- 노드와 연결된 에지를 탐색하는 시간이 매우 뛰어나다.
- 노드 개수가 커도 공간 효율이좋아 메모리 초과 에러가 발생하지 않는다.
- 실제 코딩테스트에서 많이 사용한다.
 
 

8.2 유니온 파인드 (union-find)

1) 개념

: 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘
 

2) union, find 연산

(1) union

• 각 노드가 속한 집합을 1개로 합치는 연산
• 노드 a, b가 a∈A, b∈B일 때 union(a, b)은 A∪B를 뜻한다.
• 작동 원리
  1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인한다.
  2. 동일하지 않으면 value값이 가리키는 index 위치로 이동한다.

(2) find

• 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산
• 노드 a가 a∈A일때 find(a)는 A 집합의 대표 노드를 반환한다.

 

3) 코드

int find(int n)
{
	if (n == parent[n]) return n;
	return parent[n] = find(parent[n]);
}

void unionfunc(int a, int b) {
	a = find(a);
	b = find(b);

	if (a != b) parent[b] = a;
}

 
 

8.3 위상 정렬 (topology sort)

1) 개념

: 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
 

2) 특징

• 노드 간의 순서를 찾는다. (항상 유일한 값으로 정렬되지 않는다.)
• 사이클이 없어야 한다.
• 시간 복잡도(노드 수 : V, 에지 수 : E) : O(V+E)
• 수행 과정
  1. 진입 차수가 0인 노드를 큐에 저장한다.
  2. 큐에서 데이터를 뽑아서 해당 노드를 탐색 결과에 추가하고 해당 노드가 가리키는 노드의 진입차수를 1씩 감소시킨다.
  3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 삽입한다.
  4. 큐가 빌 때까지 1~3을 반복한다.

 

3) 코드

// dg는 진입 차수를 저장하고 있는 배열

for (int i = 1; i <= n; i++) if (dg[i] == 0) q.push(i);

while (!q.empty()) 
{
	int now = q.front();
	q.pop();
	cout << now << " ";

	for (int i : arr[now]) {
		dg[i]--;
		if (dg[i] == 0) q.push(i);
	}
}

 
 

8.4 다익스트라 (dijkstra)

1) 개념

: 그래프에서 최단 거리를 구하는 알고리즘
 

2) 특징

• 출발 노드와 모든 노드 간의 최단 거리를 탐색한다.
• 에지는 모두 양수여야 한다.
• 시간 복잡도 (노드 수: V, 에지 수 : E) : O(ElogV)

 

3) 핵심 이론

1. 인접 리스트 그래프 구현하기
2. 최단 거리 배열 초기화하기
3. 값이 가장 작은 노드 고르기
4. 최단 거리 배열 업데이트하기
   • 최단 거리 업데이트 방법 : min(선택 노드의 최단거리 배열의 합+ 에지 가중치, 연결 노드의 최단 거리 배열의 값)
5. 3~4를 반복해 최단 거리 배열 완성하기

 

4) 코드

pq.push(make_pair(0, k));
dis[k] = 0;

while (!pq.empty()) {
	edge now = pq.top();

	pq.pop();
	int cv = now.second;
	if (visited[cv]) continue;
	visited[cv] = true;

	for (int i = 0; i < lst[cv].size(); i++) {
		edge tmp = lst[cv][i];

		int next = tmp.first;
		int cost = tmp.second;

		if (dis[next] > dis[cv] + cost) {
			dis[next] = dis[cv] + cost;
			pq.push(make_pair(dis[next], next));
		}
	}
}

 
 

8.5 벨만-포드 (bellman-ford-moore)

1) 개념

: 그래프에서 최단 거리를 구하는 알고리즘
 

2) 특징

• 특정 출발 노드에서 다른 모든 노드 간의 최단 거리를 탐색한다.
• 음수 가중치 에지가 있어도 수행할 수 있다.
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.
• 시간 복잡도 (노드 수: V, 에지 수 : E) : O(VE)
• 정답 배열 업데이트 방법 : D[s] != ∞ 이며 D[e] > D[s] + w일 때 D[e] = D[s] + w로 배열의 값을 업데이트한다.
• 음수 사이클 유무 확인 : 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인
  • 업데이트되는 노드가 있으면 음수 사이클이 있다. → 최단 거리를 찾을 수 없는 그래프

 

3) 핵심 이론

1. 에지 리스트를 그래프로 구현하고 최단 경로 배열 초기화하기
2. 모든 에지를 확인해 정답 배열 업데이트하기
   • 업데이트 조건과 방법 : D[s] != ∞ 이며 D[e] > D[s] + w일 때 D[e] = D[s] + w로 배열의 값을 업데이트한다.
3. 음수 사이클 유무 확인하기

 

4) 코드

dis[1] = 0;
for (int i = 1; i < n; i++) {
	for (int j = 0; j < m; j++) {
		edge m = edges[j];
		int start = get<0>(m);
		int end = get<1>(m);
		int time = get<2>(m);

		if (dis[start] != INF && dis[end] > dis[start] + time)
			dis[end] = dis[start] + time;
	}
}

bool mcycle = false;

for (int j = 0;j < m; j++) {
	edge m = edges[j];
	int start = get<0>(m);
	int end = get<1>(m);
	int time = get<2>(m);

	if (dis[start] != INF && dis[end] > dis[start] + time) mcycle = true;
}

 
 

8.6 플로이드-워셜 (floyd-warshell)

1) 개념

: 그래프에서 최단 거리를 구하는 알고리즘
 

2) 특징

• 모든 노드 간에 최단 경로 검색
• 음수 가중치 에지가 있어도 수행할 수 있다.
• 동적 계획법의 원리를 이용해 알고리즘에 접근한다.
• 시간 복잡도 (노드 수 : V) : O(V3)

3) 핵심 이론

1. 배열을 선언하고 초기화하기
2. 최단 거리 배열에 그래프 데이터 저장하기
3. 점화식으로 배열 업데이트 하기

• 도출한 플로이드-워셜 점화식 : D[S][E] = min(D[S][E], D[S][K] + D[K][E])
• 플로이드-워셜 알고리즘 로직

for 경유지 K에 관해 (1~N)
    for 출발 노드 S에 관해 (1~N)
        for 도착 노드 E에 관해 (1~N)
            D[S][E] = min(D[S][E], D[S][K]+D[K][E])

 
 

4) 코드

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= n; k++)
			if (dis[j][k] > dis[j][i] + dis[i][k]) 
                    		dis[j][k] = dis[j][i] + dis[i][k];
	}
}

 
 

8.7 최소 신장 트리 (minimum spanning tree)

1) 개념

: 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리
 

2) 특징

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다.

3) 핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파운드 배열 초기화하기
2. 그래프 데이터를 가중치 기준으로 정렬하기
3. 가중치가 낮은 에지부터 연결 시도하기
4. 과정 3을 반복하기
5. 총 에지 비용 출력하기

 

4) 코드

#include <iostream>
#include <queue>
using namespace std;

// BOJ 1197
typedef struct Edge {
	int s, e, v;
	bool operator > (const Edge& temp) const {
		return v > temp.v;
	}
}Edge;
vector<int> parent;

int find(int a) {
	if (a == parent[a]) return a;
	return parent[a] = find(parent[a]);
}

void munion(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) parent[b] = a;
}

int main() 
{
	int n, m;
	cin >>  n >> m;
	priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
	parent.resize(n + 1);

	for (int i = 0; i <= n; i++)parent[i] = i;

	for (int i = 0,s,e,v; i < m; i++) {
		cin >> s >> e >> v;
		pq.push(Edge{ s,e,v });
	}

	int useEdge = 0, result = 0;

	while (useEdge < n - 1) {
		Edge now = pq.top();
		pq.pop();
		if (find(now.s) != find(now.e)) {
			munion(now.s, now.e);
			result += now.v;
			useEdge++;
		}
	}
	cout << result;
	return 0;
}