[TIL] 22-01-03

블로그 임시 휴업. 다음에 만나요!·2022년 1월 4일

TIL

목록 보기

70/104

알고리즘 스터디

종만북) 30장 최단 경로 알고리즘 ~

백준 11657 타임머신 ~

백준 1865 웜홀 O

백준 11404 플로이드 O

백준 1613 역사 O

백준 2610 회의준비 O

알고리즘 스터디

📌참고자료

동빈나 - 다익스트라 알고리즘
https://www.youtube.com/watch?v=611B-9zk2o4

다익스트라 알고리즘 구현

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

vector<int> dist;

//adj[curNode] = {{nextNode, w}, ...}
vector<vector<pair<int, int>>> adj;

void priority_queue_dijkstra(int start){

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	dist[start] = 0;

	while (!pq.empty()){
		int curW = -pq.top().first;
		int curNode = pq.top().second;
		pq.pop();

		for (int i = 0; i < adj[curNode].size(); i++){
			int nextNode = adj[curNode][i].first;
			int nextW = adj[curNode][i].second;

			if (dist[nextNode] > curW + nextW){
				dist[nextNode] = curW + nextW;
				pq.push({ -dist[nextNode], nextNode });
			}
		}
	}
}

동빈나 - 벨만-포드 알고리즘
https://www.youtube.com/watch?v=Ppimbaxm8d8

벨만-포드 알고리즘 구현

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

const int MAX_V = 1000;
const int INF = 987654321;

//정점의 개수
int V;
//그래프의 인접 리스트 <연결된 정점 번호, 간선의 가중치>
vector<pair<int, int>> adj[MAX_V];

//음수 사이클이 있을 경우 텅 빈 배열 반환
//시작 정점 src
vector<int> bellmanFord(int src) {
	//시작점을 제외한 모든 정점까지의 최단 거리 상한 INF
	vector<int> upper(V, INF);
	upper[src] = 0;
	bool updated;

	//V번 순회
	for (int iter = 0; iter < V; ++iter) {
		updated = false;
		for (int here = 0; here < V; ++here) {
			for (int i = 0; i < adj[here].size(); ++i) {
				int there = adj[here][i].first;
				int cost = adj[here][i].second;
				//(here, there)간선을 따라 완화 시도
				if (upper[there] > upper[here] + cost) {
					//성공
					upper[there] = upper[here] + cost;
					updated = true;
				}
			}
		}
		//모든 간선에 대해 완화가 실패했을 경우 V-1번 돌 필요 없이 곧장 종료
		if (!updated) break;
	}
	//V번째 순회에도 완화가 성공했다면 음수 사이클 존재
	if (updated) upper.clear();

	return upper;
}

동빈나 - 플로이드 알고리즘
https://www.youtube.com/watch?v=9574GHxCbKc

플로이드 알고리즘 구현

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

const int MAX_V = 500;

//정점의 개수 
int V;
//그래프의 인접 행렬 표현
//adj[u][v] = u에서 v로 가는 간선의 가중치
int adj[MAX_V][MAX_V];

//플로이드-와샬 알고리즘
void floyd() {
	for (int i = 0; i < V; ++i) 
		adj[i][i] = 0;

	//i지점 -> j지점으로 이동할 때 거쳐가는 지점 K
	for (int k = 0; k < V; ++k)
		for (int i = 0; i < V; ++i)
			for (int j = 0; j < V; ++j)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}