[Algorithm] 10주차 스터디 - 우선순위큐&다익스트라 (백준 1753, 1916, 1504, 2075)

A - 백준 1753번 최단경로

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

* 문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

 

* 코드

#include <iostream>
#include <vector>
#include <queue>

#define VEC 300001
#define MAX 100000000

using namespace std;

int V, E, K;
int dis[VEC];
vector<pair<int, int>> adj[VEC];

void dijkstra(int S) {
	fill(dis, dis + VEC, MAX);
	priority_queue<pair<int, int>> pq;
	
	dis[S] = 0;
	pq.push({ 0, S });
	
	while (!pq.empty()) {
		int d = -pq.top().first;
		int u = pq.top().second;
		pq.pop();

		if (d > dis[u]) continue;
		for (int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i].first;
			int c = adj[u][i].second;
			if (dis[v] > d + c) {
				dis[v] = d + c;
				pq.push(make_pair(-dis[v], v));
			}
		}
	}
}

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
}

int main() {

	cin >> V >> E >> K;

	for (int i = 0; i < E; i++) {
		int u, v, w;

		cin >> u >> v >> w;
		adj[u].push_back(make_pair(v, w));
	}

	dijkstra(K);

	for (int i = 1; i < V+1; i++) {
		if (dis[i] == MAX) cout << "INF" << "\n";
		else cout << dis[i] << "\n";
	}

	return 0;
}

 

* 문제 풀이

최단 경로를 구하는 문제이기 때문에 시작 정점에서 각 정점의 최단 경로를 반복문으로 구하는 다익스트라 알고리즘으로 쉽게 풀 수 있었다.

 

B - 백준 1916번 최소비용 구하기

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

* 문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

 

* 코드

#include <iostream>
#include <queue>

#define VEC 100001
#define MAX 9876543210

using namespace std;

int N, M;
int dis[VEC];
vector<pair<int, int>> adj[VEC];

void dijkstra(int S) {
	fill(dis, dis + VEC, MAX);
	priority_queue<pair<int, int>> pq;

	dis[S] = 0;
	pq.push({ 0,S });

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

		if (d > dis[u]) continue;
		for (int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i].first;
			int c = adj[u][i].second;
			if (dis[v] > d + c) {
				dis[v] = d + c;
				pq.push(make_pair(-dis[v], v));
			}
		}
	}
}

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
}

int main() {
	int start, end;

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int bus_start, bus_end, bus_cost;
		cin >> bus_start >> bus_end >> bus_cost;
		adj[bus_start].push_back(make_pair(bus_end, bus_cost));
	}

	cin >> start >> end;

	dijkstra(start);

	int answer = dis[end];
	cout << answer;

	return 0;
}

 

* 문제 풀이

 A번 문제와 비슷한 맥락으로 각 도시를 정점으로, 버스의 비용을 정점을 잇는 간선으로 생각해 다익스트라 알고리즘을 사용하여 문제를 해결하였다. A번째 도시에서 다른 도시까지 가는데 드는 최소 비용을 모두 구해 B번째 도시까지 가는데 드는 최소 비용만 결과값으로 출력하였다.

 

C - 백준 1504번 특정한 최단 경로

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

* 문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

* 코드

#include <iostream>
#include <vector>
#include <queue>

#define VEC 300001
#define MAX 200000001

using namespace std;

int N, E, K, V1, V2;
int dis[VEC];
vector<pair<int, int>> adj[VEC];

void dijkstra(int S) {
	fill(dis, dis + VEC, MAX);
	priority_queue<pair<int, int>> pq;

	dis[S] = 0;
	pq.push({ 0, S });

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

		if (d > dis[u]) continue;
		for (int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i].first;
			int c = adj[u][i].second;
			if (dis[v] > d + c) {
				dis[v] = d + c;
				pq.push(make_pair(-dis[v], v));
			}
		}
	}
}

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
}

int main() {
	bool flag1, flag2;
	flag1 = flag2 = true;

	cin >> N >> E;

	for (int i = 0; i < E; i++) {
		int a, b, c;

		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, c));
	}

	cin >> V1 >> V2;

	dijkstra(1);
	int result1 = dis[V1];
	int result2 = dis[V2];
	if (dis[V1] == MAX) flag1 = false;
	if (dis[V2] == MAX) flag2 = false;

	dijkstra(V1);
	result1 += dis[V2];
	result2 += dis[V2] + dis[N];
	if (dis[V2] == MAX) flag1 = false, flag2 = false;
	if (dis[N] == MAX) flag2 = false;

	dijkstra(V2);
	result1 += dis[N];
	if (dis[N] == MAX) flag1 = false;
	
	int answer;
	if (result1 < result2) answer = result1;
	else answer = result2;
	
	if (!flag1 && !flag2) answer = -1;

	cout << answer << "";
	return 0;

}

 

* 문제 풀이

 최단 경로 문제이기 때문에 역시 다익스트라 알고리즘을 적용해 문제를 풀어야 하지만, 두 정점을 반드시 지나야한다는 조건 때문에 변형이 필요하다. 그래서 총 2가지의 최단 경로를 계산해, 최소값을 출력해주는 방식으로 문제를 해결하였다.

(1) 1번 정점 -> A번 정점 -> B번 정점 -> N번 정점

(2) 1번 정점 -> B번 정점 -> A번 정점 -> N번 정점

 각 경로(1번 예시에서는 {1, A}, {A, B}, {B, N})의 최단 경로를 구해주고, 모두 더해준 다음에 (1)과 (2)의 최소값을 구해 결과로 출력하였다.

 

D - 백준 2075번 N번째 큰 수

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

* 문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

 

* 코드

#include <iostream>
#include <queue>

using namespace std;

int N, num;
priority_queue<long long> q;

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
}

int main() {
	init();

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> num;
			q.push(-num);
			if (q.size() > N) q.pop();
		}
	}

	cout << -q.top();
	return 0;
}

 

* 문제 풀이

 입력값 중에서 N번째로 큰 수를 계산하기 위해 우선순위 큐라는 자료구조를 사용하였다. 우선순위 큐에 입력값을 넣으면 오름차순으로 값이 자동 정렬되기 때문에 사이즈가 N을 넘으면 pop() 메소드로 가장 작은 값을 제거하였다. 결과값으로 큐의 가장 위 쪽에 있는 값을 출력한다.