이것 저것 &

문제링크: https://www.acmicpc.net/problem/11404

문제 제목처럼 플로이드 와샬 알고리즘 문제이지만.. 다익스트라로 풀었다... (속도차이도 크게 안나요.. 취존...)

접근방식

1. 전형적인 최단거리를 구하는 문제 

2. 다만 모든 좌표에 한해서 최단거리를 구해야하기 때문에 플로이드 와샬문제지만 

쿨하게 다익스트라로 모든 좌표에 대한 최단 거리를 구하고 출력해주었다. 

문제풀이 

1. 전형적인 다익스트라로 구현

2. 모든 점에서 다익스트라 호출

주의할 점은 연결이 불가한 경우엔 0을 출력하는것

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

int n, m;
vector <pair<int, int>> vec[101];
int dist[101];

void dijkstra(int num) {
	priority_queue <pair<int, int>> que;
	que.push(make_pair(0, num));
	dist[num] = 0;

	while (!que.empty()) {
		int cost = que.top().first * -1;
		int cur = que.top().second;
		que.pop();

		for (int i = 0; i < vec[cur].size(); i++) {
			int before_v = dist[vec[cur][i].first];
			int current_v = dist[cur] + vec[cur][i].second;

			if (current_v < before_v) {
				dist[vec[cur][i].first] = current_v;
				que.push(make_pair(current_v*-1, vec[cur][i].first));
			}

		}


	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	int from, to, cost;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
	}
	
	for (int i = 1; i <= n; i++) { // 매 줄마다 반복할거

		for (int j = 1; j <= n; j++)
			dist[j] = 2000000000;

		dijkstra(i);

		for (int j = 1; j <= n; j++) {
			if (dist[j] == 2000000000)
				printf("0 ");
			else
				printf("%d ", dist[j]);
		}
		printf("\n");
	}

	return 0;
}

문제링크: https://www.acmicpc.net/problem/9370

다익스트라 + 구현 문제 

접근방식

1. 최단 거리 탐색에서 다익스트라로 구현하면 되겠다 생각

2. 아래 문제와 비슷한 방식

https://gusdnr69.tistory.com/239?category=799066 

결국 s -> g -> h -> 목표 지점 또는 s -> h -> g -> 목표 지점으로 이동할 때의 최소값이 

s -> 목표지점으로 도달하는 값이 똑같은지 비교하는 문제 

3. 다익스트라를 3번 호출해서 구현하자 

문제풀이 

1. 다익스트라는 일반적인 형태와 똑같이 구현. 다만 매개변수에 배열을 넣어서 해당 배열을 채워 주는 구조로 

2. dist배열을 s에서 시작할 때, g에서 시작할 때, h에서 시작할 때 총 3개를 만들고 다익스트라 함수도 총 3번 호출

3.  min( s-g-h-목표 지점, s-h-g-목표지점)이  s-목표지점과 같은지 확인  

정답 코드

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

int T, n, m, t, s, g, h;
int a, b, d, temp;

vector <int> destin; //목적지 위치, 시작점에서 다이렉트로 도달할 때 거리를 저장할거
int dist_s[2001];
int dist_g[2001];
int dist_h[2001];
vector <pair<int,int>> arr[2001];

void dijkstra(int start, int dist[2001]) {
	priority_queue <pair<int,int>> que;
	que.push(make_pair(0, start));
	dist[start] = 0;

	while (!que.empty()) {
		int cost = que.top().first *  -1;
		int cur = que.top().second;
		que.pop();


		for (int i = 0; i < arr[cur].size(); i++) {
			int before_v = dist[arr[cur][i].first];
			int current_v = cost + arr[cur][i].second;
			if (before_v > current_v) {
				dist[arr[cur][i].first] = current_v;
				que.push(make_pair(current_v*-1, arr[cur][i].first));
			}
		}

	}



}



int main() {
	

	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d", &n, &m, &t);
		scanf("%d %d %d", &s, &g, &h);
		
		
		//초기화 
		destin.clear();
		for (int i = 1; i <= 2000; i++) {
			arr[i].clear();
			dist_s[i] = 2000000000;
			dist_g[i] = 2000000000;
			dist_h[i] = 2000000000;
		}
		
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &a, &b, &d);
			arr[a].push_back(make_pair(b, d));
			arr[b].push_back(make_pair(a, d));
		}

		for (int i = 0; i < t; i++) {
			scanf("%d", &temp);
			destin.push_back(temp);
		}

		sort(destin.begin(), destin.end()); // 오름차순으로 미리 정렬해둠	

		dijkstra(s, dist_s);
		dijkstra(g, dist_g);
		dijkstra(h, dist_h);

		

		for (int i = 0; i < destin.size(); i++) {

			if (dist_s[destin[i]] == (dist_s[g] + dist_g[h] + dist_h[destin[i]]))
				cout << destin[i] << ' ';
			else if(dist_s[destin[i]] == (dist_s[h] + dist_h[g] + dist_g[destin[i]]))
				cout << destin[i] << ' ';
		}
		cout << endl;


		/*
		cout << endl;
		for (int i = 1; i <= n; i++) {
				cout << dist2[i] << ' ';
		}
		cout << endl;
		*/

	}

	return 0;
}

문제링크: https://www.acmicpc.net/problem/11779

다익스트라 문제이고, 추가 사항은 최소 경로를 구해야 하는 것이었습니다.

다익스트라는 일반적인 우선순위 큐 방식을 사용하였고, 경로를 저장하기 위해서는 자신의 출발지 값을 저장하게끔 구성을 해주었습니다.

접근방식

1. 일반적인 다익스트라 방식을 생각함

2. 최소 경로를 구하기 위해서 배열을 생성하고 출력

문제풀이 

1. 일반적인 다익스트라 구현

2. 최소 경로를 구하기 위해서 배열을 생성함

해당배열에는 자신의 부모정점을 저장함.

ex) 1->3이면 arr[3] = 1 

3. 해당 배열에서 while문을 사용하여 결과를 도출함 

일부 예외처리를 신경써주어야 했음.

아래 처럼 탐색할 필요없는 정점이라면 가지치기를 해주어야 통과할 수 있는 문제.

		if (cost > dist[cur])
			continue;

가지치기를 해주어야 하는점이 꽤나 까다로운 문제였습니다.

정답코드입니다.

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

int cnt = 0;


int dist[1001];
int before_val[1001] = { 0, };
vector <pair<int, int>> vec[1001];
int n, m, s, e; // 도시 개수, 버스의 개수, 출발지, 도착지 

void dijkstra() {

	priority_queue <pair<int, int>> pq;
	pq.push(make_pair(0, s));
	dist[s] = 0; 
	while (!pq.empty()) {

		int cost = - pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		if (cost > dist[cur])
			continue;

		for (int i = 0; i < vec[cur].size(); i++) {
			int ncost = vec[cur][i].second;
			int ncur = vec[cur][i].first;

		
			if (dist[ncur] > cost + ncost) {
				dist[ncur] = ncost + cost;
				pq.push(make_pair(-dist[ncur], ncur));
				before_val[ncur] = cur;
			}
		}



	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		dist[i] = 2000000000;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		vec[a].push_back(make_pair(b, c));
	}

	cin >> s >> e;
	dijkstra();

	vector <int> arr;
	arr.push_back(e);
	int val = before_val[e];
	while (val) {
		arr.push_back(val);
		val = before_val[val];
	}
	

	cout << dist[e] << endl;
	cout << arr.size() << endl;
	for (int i = arr.size() - 1; i >= 0; i--) {
		cout << arr[i] << " ";
	}
	cout << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/4485

최단거리를 도출하는 문제입니다. 

접근방식

1. 일반적인 bfs 방식과 다익스트라 방식 2가지를 생각함

3. 수의 범위가 125*125로 비교적 작기 때문에 둘다 가능할 것이라고 생각함

결과적으로 둘다 ok! 다익스트라가 4ms bfs가 8ms

4. 전형적인 방식으로 구현하자!

문제풀이 

1. 우선 bfs로 구현함

일반적인 bfs 방식으로 구현이 가능

2. 다익스트라 방식은 dist배열을 생성하고 가장 작은 cost값들을 pop하면서 진행

3. 코드가 간결하니 코드를 보고 이해하는게 빠를 듯

아래는 bfs 방식 정답 코드

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

int y_ar[4] = { 0,0,-1,1 };
int x_ar[4] = { 1,-1,0,0 };
int n;
int arr[130][130];
int dist[130][130];

void bfs() {

	queue <pair<int, int>> pq;

	pq.push(make_pair(0, 0));
	dist[0][0] = arr[0][0];
    
	while (!pq.empty()) {
		
		int y = pq.front().first;
		int x = pq.front().second;
		pq.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + y_ar[i];
			int nx = x + x_ar[i];
			

			if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
				if ( dist[ny][nx] > dist[y][x] + arr[ny][nx]) {
					dist[ny][nx] = dist[y][x] + arr[ny][nx];
					pq.push(make_pair(ny, nx));
				}
			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int cnt = 1;

	while (1) {
		cin >> n;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
				dist[i][j] = 2000000000;
			}
		
		bfs();
		cout << "Problem " << cnt++ << ": " << dist[n - 1][n - 1] << "\n";
	}

	return 0;
}

아래는 다익스트라 알고리즘 방식

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

typedef struct {
	int y;
	int x;
}p;

int y_ar[4] = { 0,0,-1,1 };
int x_ar[4] = { 1,-1,0,0 };
int n;
int arr[125][125];
int dist[125][125];

void dijkstra() {

	priority_queue <pair<int, pair<int, int>>> pq;
	pq.push(make_pair(-1 * arr[0][0], make_pair(0, 0)));
	dist[0][0] = arr[0][0];

	while (!pq.empty()) {
		//int cost = pq.top().first * -1;
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		pq.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + y_ar[i];
			int nx = x + x_ar[i];
			int ncost = arr[ny][nx];

			if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
				int before_v = dist[ny][nx];
				int current_v = dist[y][x] + ncost;
				if (before_v > current_v) {
					dist[ny][nx] = current_v;
					pq.push(make_pair(-1 * current_v, make_pair(ny, nx)));
				}
			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int cnt = 1;

	while (1) {
		cin >> n;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
				dist[i][j] = 2000000000;
			}

		dijkstra();
		cout << "Problem " << cnt++ << ": " << dist[n - 1][n - 1] << "\n";
		
	}


	return 0;
}

문제링크: https://www.acmicpc.net/problem/1504

다익스트라 문제입니다.

차이점은 v1과 v2를 들렸다가 n으로 도달해야한다는 점입니다.

그렇다면, 경우는 2가지 입니다.

1->v1->v2->n

1->v2->v1->n

각각의 경우에 맞춰서 다익스트라 함수를 사용해주면 됩니다.

주의할 점은 v1,v2,n 모두 도달이 가능해야 한다는 점입니다. 

아래는 정답 코드입니다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define INF 2000000000

int n, e, v1, v2;
vector <pair<int, int>> vec[801];
int dist[801];

int dijkstra(int sn, int en) {
	priority_queue <pair<int, int>> pq;
	pq.push(make_pair(0, sn));

	while (!pq.empty()) {
		int cost = -1 * pq.top().first;
		int node = pq.top().second;
		pq.pop();

		for (int i = 0; i < vec[node].size(); i++) {
			int current_val = dist[node] + vec[node][i].second;
			int before_val = dist[vec[node][i].first];

			if (current_val < before_val) {
				dist[vec[node][i].first] = current_val;
				pq.push(make_pair(current_val*-1, vec[node][i].first));
			}

		}
	}

	return dist[en];

}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> e;
	for (int i = 1; i <= e; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
	}
	cin >> v1 >> v2;

	for (int i = 1; i <= n; i++)
		dist[i] = INF; 
	dist[1] = 0;
	dijkstra(1, n);

	if (dist[v1] == INF || dist[v2] == INF || dist[n] == INF) {
		cout << -1 << endl;
		return 0;
	}


	long long result1 = 0;
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[1] = 0;
	result1 += dijkstra(1,v1);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v1] = 0;
	result1 += dijkstra(v1, v2);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v2] = 0;
	result1 += dijkstra(v2, n);

	long long result2 = 0;
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[1] = 0;
	result2 += dijkstra(1, v2);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v2] = 0;
	result2 += dijkstra(v2, v1);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v1] = 0;
	result2 += dijkstra(v1, n);


	cout << min(result1, result2) << endl;
	return 0;
}

문제링크:https://www.acmicpc.net/problem/1916

1753번 문제와 똑같습니다. 한 정점에서의 최단경로를 구하기 위해서 다익스트라를 구현해야 합니다.  

다익스트라를 구현할때 우선순위 큐를 사용해야 합니다. 

min-heap을 이용해서 가장 작은 경로값 부터 적용해주며 진행하여야 컴팩트하게 구현할 수 있습니다.(일반 큐를 사용하면 틀립니다.)

정답코드입니다.

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


int a = 0, b = 0; // 출발지, 도착지
int n = 0; // 도시의 개수
int m = 0; // 버스의 개수

vector <int> result;
vector <pair<int, int>> m_arr[1001];

void soultion(int start_index) {

	for (int i = 0; i <= n; i++)
		result.push_back(1000000000); // 최대 값으로 초기화

	priority_queue <pair <int, int >> que; //우선 순위 큐 생성
	que.push(make_pair(0,start_index));

	while (que.empty() == 0) {
		int cost = - que.top().first;
		int destination = que.top().second;
		que.pop();

		if (result[destination] < cost) continue; // 기존 경로가 더 가까우면 continue

		for (int i = 0; i < m_arr[destination].size(); i++) {
			int adjacent_cost =  m_arr[destination][i].second ;
			int adjacent_des = m_arr[destination][i].first;

			if (result[adjacent_des] > adjacent_cost + cost ) {
				result[adjacent_des] = adjacent_cost;
				que.push(make_pair(-result[adjacent_des], adjacent_des));
			}
		}

	}

}

int main(){
	cin >> n;
	cin >> m;
	int u, l, k;
	for (int i = 0; i < m; i++) {
		cin >> u >> l >> k;
		m_arr[u].push_back(make_pair(l, k)); // 
	}
	cin >> a >> b;

	soultion(a);

	cout << result[b] << endl;

	return 0;
}

https://gusdnr69.tistory.com/134?category=799066

위 문제도 참고하세요. 

다익스트라 알고리즘을 이용해서 해결해야 하는 문제입니다.

왜? 그냥 que를 이용해서 구현하면 안되나 생각했습니다. 결과는 

인접하는 정점으로 이동할때는 최소경로값으로 먼저 이동하면서 큐에 들어가는 갯수를 최소화 시켜줘야 합니다.

하나의 정점에서 모든 정점으로 이동하는 최소경로값 (양수만) 이기 때문에 해당 다익스트라 기법을 구현하면 됩니다.  

https://gusdnr69.tistory.com/133

그리고 또 조심하셔야 할게 vector를 사용하지 않고 20000 X 20000 배열을 생성하면 메모리 초과입니다..

이 두 가지를 조심하며 작성해주시면 됩니다.  

구현하는 방법은 bfs와 흡사합니다.

정답코드입니다.

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

int v = 0, e = 0, k = 0;

vector <pair <int, int>> arr[20001];
vector <int> result;

void solution(){

	for (int i = 0; i < v + 1; i++)
		result.push_back(123456789);

	priority_queue <pair <int, int>> que; //우선순위큐
	que.push(make_pair(0, k)); //초기비용0 과 시작점 // min 우선순위큐를 사용하기 위해서 음수값을 넣어주는 행동

	
	while (!que.empty() ) {
		int cost = -que.top().first; // -를 다시 붙여준다. 
		int pos = que.top().second;
	
		que.pop();

		if (result[pos] < cost) continue;
		
		for (int i = 0; i < arr[pos].size(); i++) {
			int adjacency_pos = arr[pos][i].first;
			int adjacency_cost = arr[pos][i].second;

			if (adjacency_cost + cost < result[adjacency_pos]) {
				result[adjacency_pos] = adjacency_cost + cost;
				que.push(make_pair(-result[adjacency_pos], adjacency_pos));
			}

		}
		
		
	}
	
	

}

int main() {

	int u, vv, w;
	
	cin >> v >> e >> k;
	

	for (int i = 0; i < e; i++) {
		cin >> u >> vv >> w;
		arr[u].push_back(make_pair(vv, w));
	}

	solution();
	
	for (int i = 1; i < result.size(); i++) {
		if (i == k)
			cout << 0 << '\n';
		else if (result[i] == 123456789)
			cout << "INF" << '\n';
		else
			cout << result[i] << '\n';
	}
	


	return 0;
}