언제나 처음처럼

[문제 링크]

문제를 보고 생각난 알고리즘은 플로이드-와샬 알고리즘이었다. 하지만 N이 최대 800이므로 O(N^3)이면 약 5억이 넘게 되어 시간초과가 날 것이라 생각하고 다익스트라 알고리즘으로 구현하였다.

정점 v1과 v2를 반드시 지나야 하기 때문에 1부터 N까지 갈 수 있는 방법은 아래 두가지 경로만 가능하다.

경로 1) dist[1][v1] -> dist[v1][v2] -> dist[v2][N] 

경로 2) dist[1][v2] -> dist[v2][v1] -> dist[v1][N]

dist[v1][v2] 와 dist[v2][v1] 의 최단경로는 서로 같으므로, 3개의 정점 1, v1, N 을 출발점으로 하는 다익스트라 알고리즘을 수행하여 최단경로를 계산해주면 된다.

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

// INF를 987654321로 할 경우
// 62~63 라인에서 int의 최대 범위 넘어갈 수 있다.
const int INF = 700000000;
int N, E;
vector<vector<pair<int, int>>> adj(801);
vector<vector<int>> allDist(801, vector<int>(801, INF));

void dijkstra(int start) {
	vector<int> dist(N + 1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

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

		if (dist[here] < cost) continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (dist[there] > nextCost) {
				dist[there] = nextCost;
				pq.push({ -nextCost, there });
			}
		}
	}

	allDist[start] = dist;
}

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

	cin >> N >> E;

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

	int v1, v2;
	cin >> v1 >> v2;

	dijkstra(1);
	dijkstra(v1);
	dijkstra(N);

	int path1 = allDist[1][v1] + allDist[v1][v2] + allDist[v2][N];
	int path2 = allDist[1][v2] + allDist[v1][v2] + allDist[v1][N];

	int result = min(path1, path2);

	if (result >= INF)
		cout << -1 << endl;
	else
		cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 168 day

[문제 링크]

방향그래프를 만든 다음 최단 경로 알고리즘을 통해 간단히 풀 수 있는 문제였다.

처음 풀었을 땐 플로이드-와샬 알고리즘으로 구현해서 정답을 받았는데, 생각해보니 N이 최대 1000이기 때문에 시간복잡도가 O(N^3)인 플로이드-와샬 알고리즘을 사용하면 최악의 경우 10억만큼의 시간이 걸리게 된다. 입력데이터가 부실했기 때문에 운좋게 통과했다고 생각한다.

따라서 다익스트라 알고리즘을 사용해서 다시 구현하였다.

//추가 : 질문게시판에서 시간복잡도를 더 줄이는 방법에 대한 힌트를 발견하였다.

도착지점이 X로 정해져 있기 때문에 모든 정점의 최단 경로를 다 구할 필요 없이 정점으로 들어오는 간선들의 집합과 정점에서 나가는 간선들의 집합을 분리한 다음, 정점 X에서 들어오는 간선과 나가는 간선을 대상으로 두번의 다익스트라를 수행하면 문제를 해결할 수 있다.

// 플로이드-와샬 알고리즘 사용

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

const int INF = 987654321;
vector<vector<int>> adj(1001, vector<int>(1001, INF));

void floyd(int N) {
	for (int i = 1; i <= N; i++) {
		adj[i][i] = 0;
	}

	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

int main(void) {
	int N, M, X;
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adj[A][B] = W;
	}

	floyd(N);

	int result = 0;
	for (int i = 1; i <= N; i++) {
		result = max(result, adj[i][X] + adj[X][i]);
	}

	cout << result << endl;

	return 0;
}

// 다익스트라 알고리즘 사용

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

const int INF = 987654321;
int N, M, X;
vector<pair<int, int>> adj[1001];
vector<vector<int>> allTownDist(1001);

void dijkstra(int start) {
	vector<int> dist(N+1, INF);
	dist[start] = 0;
	
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

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

		if (dist[here] < cost) continue;
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (dist[there] > nextCost) {
				dist[there] = nextCost;
				pq.push({ -nextCost, there });
			}
		}
	}

	allTownDist[start] = dist;
}

int main(void) {
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adj[A].push_back({ B, W });
	}

	for (int i = 1; i <= N; i++)
		dijkstra(i);

	int result = 0;
	for (int i = 1; i <= N; i++) 
		result = max(result, allTownDist[i][X] + allTownDist[X][i]);

	cout << result << endl;

	return 0;
}

// 다익스트라 2번으로 문제를 해결하는 코드

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

const int INF = 987654321;
int N, M, X;
vector<pair<int, int>> adjIn[1001];
vector<pair<int, int>> adjOut[1001];

vector<int> inDist(1001);
vector<int> outDist(1001);

void dijkstra(int start, int type) {
	vector<int> dist(N + 1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	
	if (type == 1) {
		while (!pq.empty()) {
			int here = pq.top().second;
			int cost = -pq.top().first;
			pq.pop();

			if (dist[here] < cost) continue;
			for (int i = 0; i < adjIn[here].size(); i++) {
				int there = adjIn[here][i].first;
				int nextCost = adjIn[here][i].second + cost;

				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.push({ -nextCost, there });
				}
			}
		}
		inDist = dist;
	}

	else {
		while (!pq.empty()) {
			int here = pq.top().second;
			int cost = -pq.top().first;
			pq.pop();

			if (dist[here] < cost) continue;
			for (int i = 0; i < adjOut[here].size(); i++) {
				int there = adjOut[here][i].first;
				int nextCost = adjOut[here][i].second + cost;

				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.push({ -nextCost, there });
				}
			}
		}
		outDist = dist;
	}
}

int main(void) {
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adjIn[A].push_back({ B, W });
		adjOut[B].push_back({ A, W });
	}

	dijkstra(X, 1); // 정점으로 들어오는 간선들의 최단경로
	dijkstra(X, 2); // 정점에서 나가는 간선들의 최단경로

	int result = 0;
	for (int i = 1; i <= N; i++) 
		result = max(result, inDist[i] + outDist[i]);

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 167 day

[문제 링크]

시작지점(1,1) 에서 도착지점(N,M) 으로 가는 최단 경로를 구하는 문제였다.

벽을 최대한 안부시는 경로로 이동해야 하기 때문에 방문표시를 하면 안된다.

따라서, 다익스트라 알고리즘을 이용하여 구현하였다.

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

const int INF = 987654321;
int N, M;
char board[101][101];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int dijkstra() {
	vector<vector<int>> dist(101, vector<int>(101, INF));
	dist[1][1] = 0;

	priority_queue <pair<int, pair<int, int>>> pq;
	pq.push({ 0, {1,1} });

	while (!pq.empty()) {
		int hy = pq.top().second.first;
		int hx = pq.top().second.second;
		int isBreak = -pq.top().first;
		pq.pop();

		if (dist[hy][hx] < isBreak) continue;

		for (int i = 0; i < 4; i++) {
			int ny = hy + dy[i];
			int nx = hx + dx[i];

			if (ny > 0 && ny <= N && nx > 0 && nx <= M) {
				int nextBreak = isBreak + board[ny][nx] - '0';

				if (dist[ny][nx] > nextBreak) {
					dist[ny][nx] = nextBreak;
					pq.push({ -nextBreak, {ny, nx} });
				}
			}
		}
	}

	return dist[N][M];
}

int main(void) {
	cin >> M >> N;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> board[i][j];

	cout << dijkstra() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 165 day

[문제 링크]

다익스트라 알고리즘을 이용하는 문제였다.

입력으로 주어지는 버스의 정보를 간선으로 연결하고, 출발 도시를 시작 정점으로 하는 다익스트라 알고리즘을 수행하면 출발 도시에서 모든 도시로 가는 최소 비용을 구할 수 있다. 여기서 도착 도시로 가는 최소 비용을 찾아 출력해주면 원하는 결과를 얻을 수 있다.

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

const int INF = 987654321;
int N, M;
vector<pair<int, int>> adj[1001];

int dijkstra(int start, int arrive){
	vector<int> dist(N+1, INF);
	dist[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

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

		if (dist[here] < cost) continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (dist[there] > nextCost) {
				dist[there] = nextCost;
				pq.push({ -nextCost, there });
			}
		}
	}

	return dist[arrive];
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		adj[s].push_back({ e, w });
	}

	int start, arrive;
	cin >> start >> arrive;

	cout << dijkstra(start, arrive) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 164 day

[문제 링크]

한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제였다.

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

const int INF = 987654321;
int V, E;
vector<pair<int, int>> adj[20001];

vector<int> dijkstra(int start)
{
	vector<int> dist(V+1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

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

		if (dist[here] < cost) continue;
		
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;

			if (dist[there] > nextDist)
			{
				dist[there] = nextDist;
				pq.push({ -nextDist, there });
			}
		}
	}

	return dist;
}

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

	cin >> V >> E;

	int start;
	cin >> start;

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

		adj[u].push_back({ v,w });
	}

	vector<int> result = dijkstra(start);

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

	return 0;
}

알고리즘 200일 프로젝트 - 163 day