백준 5719번 : 거의 최단 경로

문제 접근

---

    거의 최단 경로를 구해야한다. 이 문제에서 '거의 최단 경로'란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 따라서 다익스트라 알고리즘을 통해 최단 경로에 포함되는 도로를 찾은 후, 해당 도로를 배제한 뒤 다시 다익스트라 알고리즘을 통해 거의 최단 경로를 찾도록 구현했다.

 

 

문제 코드

---

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

using namespace std;

int N, M;
int S, D;
int U, V, P;
int ans;

// 인접 노드들의 정보가 담겨있는 vector 이다.
vector<vector<pair<int, int>>> adj;
// 최단 경로의 포함되는 장소의 부모를 저장하는 vector 이다.
vector<vector<int>> parent;
// 최단 경로를 배제할 때 중복해서 처리하지 않기 위해 방문 여부를 확인하는 vector 이다.
vector<bool> check;

// 다익스트라 알고리즘을 사용하여 최단 경로를 구하는 함수이다.
int shortestRoad()
{
    // n 번 노드까지의 최단 거리를 저장하는 vector 이다. 
    // 초기값은 도로의 최대 개수 10000 에, 최대 길이 1000 을 곱한 뒤 1 을 더한 값으로 설정했다.
	vector<int> dist(N + 1, 10000001);
	priority_queue<pair<int, int>> q;

	dist[S] = 0;
	q.push({ 0, S });

	while (!q.empty())
	{
		int here = q.top().second;
        // priority queue 의 default 값은 오름차순이기에 길이에 -1을 곱해 내림차순으로 바꿔주었다.
		int cost = -q.top().first;
		q.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;
			
            // 배제된 도로의 길이를 -1 로 설정했다. 따라서 길이가 -1 인 도로가 나오면 무시했다.
			if (adj[here][i].second == -1)
				continue;
			
            // 길이가 같다면 또 다른 최단 경로가 될 수 있다.
            // 따라서 clear 하지 않고 push 하도록 구현했다.
            // 또한 길이가 같은 경우 중복해서 처리할 필요가 없기에 queue 에 따로 push 하지 않았다.
			if (nextDist == dist[there])
			{
				parent[there].push_back(here);
			}
			
            // 최단 거리가 갱신됐다면 기존의 부모 노드들 또한 최단 경로가 아니게 된다.
           	// 따라서 clear 후 최단 경로가 되도록 하는 부모 노드를 push 했다. 
			else if (nextDist < dist[there])
			{
				parent[there].clear();
				parent[there].push_back(here);

				dist[there] = nextDist;
				q.push({ -nextDist, there });
			}
		}
	}

	return dist[D];
}

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

	while (cin>>N>>M && (N||M))
	{
		adj.assign(N + 1, vector<pair<int, int>>());
		parent.assign(N + 1, vector<int>());
		check.assign(N + 1, false);

		cin >> S >> D;

		while (M--)
		{
			cin >> U >> V >> P;
			adj[U].push_back({ V, P });
		}
		
        // D 까지의 최단 거리가 초기값과 같다면 경로가 없는 것으로 판단해서 -1 을 출력하도록 했다.
		if (shortestRoad() == 10000001)
		{
			cout << "-1\n";
			continue;
		}

		queue<int> erase;

		erase.push(D);
        
		while (!erase.empty())
		{
			int place = erase.front();
			erase.pop();

			if (check[place])
				continue;

			check[place] = true;

			for (int i = 0; i < parent[place].size(); ++i)
			{
				for (int j = 0; j < adj[parent[place][i]].size(); ++j)
				{
                    // place 의 부모 노드에서 place 까지 오는 경로가 있다면 배제했다.
					if (adj[parent[place][i]][j].first == place)
					{
						erase.push(parent[place][i]);
						adj[parent[place][i]][j].second = -1;
					}
				}
			}
		}

		ans = shortestRoad();

		if (ans == 10000001)
			cout << "-1\n";

		else
			cout << ans << '\n';
	}
}

 

 

느낀 점

---

    이 문제는 작년 이 맘때쯤 처음으로 풀었던 플레티넘 문제이다. 당시 이 문제로 solved.ac 골드 티어를 가서 기뻐했었는데, 몇 달 전 재채점되면서 '메모리 초과' 처리되었다.

 

    이번에 군대에 있던 친구들과 다시 풀어보기로 해서 처음부터 다시 구현했는데, 그래도 PS 실력이 약간은 늘었는지 훨씬 수월하고 빠르게 풀 수 있었다.

 

    이제까지 얼마 안 되는 문제를 풀어보면서 TLE (시간 초과)는 받아본 적 있어도, MLE (메모리 초과)는 받아본 적이 몇 번 없었는데, 어떻게 메모리를 줄일 수 있을지 고민해볼 수 있는 좋은 시간이었다.