백준 5719번 : 거의 최단 경로

문제 접근

---

처음에는 일단 구현부터 해보려고 단순하게 최단 경로를 지우고 다시 최단 경로를 찾는 걸 생각했다. 이때 첫 번째 최단 경로의 길이를 변수에 할당해서 다음 최단 경로의 길이가 이와 같으면 이 또한 기존의 최단 경로라고 생각해서 지우기를 반복했다. 하지만 첫 번째 시도의 최단 경로를 지우는 순간, 다른 최단 경로가 최단 경로가 아니게 될 수 있기에 이 방법은 틀렸다.

 

그래서 두 번째로, 최단 경로를 다 모아서 한 번에 지우는 방식을 구현했다. 어떻게 구현해야 할까 고민하던 중 다익스트라 알고리즘의 priority_queue 가 보여서 여기에도 사용할 수 있을 것 같았다. 갱신할 때 부등호 처리해주고 자동으로 정렬한 뒤 eraseEdge()에서 child까지의 최단 거리가 같으면 경로가 다른 최단 거리라고 판단해서 parent를 list에 push, 같지 않으면 나머지를 pop() 하도록 했다. 최단 거리 경로에 list에 저장된 parent 들을 다음 eraseEdge()에서 재귀로 반복해서 시작점까지 지워주도록 구현했다.

 

돌려보니 성공했다! 플레티넘 첫 문제! 이 문제로 골드5가 됐다!

 

 

이 문제를 풀 때 구조화를 하지 않고 아이디어만으로 풀다보니 복잡한 구조에 어리벙벙해서 본능에 맡겨 푼 것 같다. '어.. 어.. 이렇게 이렇게?' 하면서 구현을 한 뒤 제출할 때 확신이 있긴 했는데 정말로 성공하니 기분이 너무 좋다! 히히 :) 스파게티 코드가 된 것 같아서 아쉽긴 한데 구조화하고 설계하는 능력을 키우다 보면 전역하기 전에 깔끔한 코드를 작성할 수 있게 되지 않을까?

 

느낀 점!

1. 문제를 풀기 전에 수도 코드든 뭐든 무슨 기능이 구현될거고 어떤 구조로 설계할 건지 계획하자!

2. 문제 세부 조건까지 잘 읽었다! 다만 읽는 선에서 멈추지 말고, 이 조건으로 인해 생길 문제에 대해 예상해보자!

3. 질문 글에서 테스트케이스 찾는 것도 좋지만, 스스로 생각해보고 반례를 만들어보자!

 

코드 분석 후!

Parent 를 priority_queue 로 만들고 최단 경로 확인할 필요없이, 각 노드까지의 최단 경로 저장하는 vector 들을 만들어서 갱신할때마다 넣어주면 된다. 특정 노드까지의 최단 거리가 같다면 이 또한 최단 경로이기에 q 에 갱신하지 않고 vector 에만 넣어주면 깔끔하게 처리할 수 있다. 기존 특정 노드까지의 최단 거리가 갱신되는 경우 이 경로 vector 를 clear() 해주고 다시 push_back() 하면 된다. 내 방법이 틀린 건 아니지만 이렇게 풀면 조금 더 깔끔하게 구현할 수 있을 것 같다.

 

 

문제 코드

---

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

using namespace std;

int N, M, S, D, U, V, P;
const int INF = 10000001;
vector<pair<int, int>> adj[500];
// 선행 노드를 저장하는 우선순위 큐. first -> dist, second -> parent node
// priority_queue 는 값이 dist 를 기준으로 정렬되어 있으면 편할 거 같아서 사용했다.
priority_queue<pair<int,int>> Parent[500];

int almost_shotest(int size, int src)
{
	vector<int> dist(size, INF);
	priority_queue<pair<int,int>> q;
	
	dist[src] = 0;
	q.push(make_pair(0,src));
	
	while(!q.empty())
	{
		int here = q.top().second;
		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].second;
			int nextDist = cost + adj[here][i].first;
			
			if(nextDist <= dist[there])
			{
				dist[there] = nextDist;
				q.push(make_pair(-nextDist, there));
                // there 를 갱신할 때 there 의 이전 노드인 here 와 dist 를 저장.
				Parent[there].push(make_pair(-nextDist, here));
			}
		}
	}
	
	return dist[D];
}

void eraseEdge(int child, int min_dist)
{
	// child 의 이전 노드들을 저장하는 vector.
	vector<int> list;
	
	while(!Parent[child].empty())
	{
    	// min_dist : child 까지의 최단 거리
		if(-Parent[child].top().first == min_dist)
		{
			int parent = Parent[child].top().second;
			for(int i=0; i<adj[parent].size(); ++i)
			{
				if(adj[parent][i].second == child)
				{
					adj[parent].erase(adj[parent].begin()+i);
                    // child 까지의 최단 거리가 같다면 찾아서 지우고 이전 노드를 push_back()
					list.push_back(parent);
					break;
				}
			}
		}
		
		Parent[child].pop();
	}
	
    // 시작점까지 재귀로 최단 거리 경로를 탐색하며 eraseEdge.
	for(int i=0; i<list.size(); ++i)
		if(list[i]!=S)
			eraseEdge(list[i], -Parent[list[i]].top().first);
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	while(cin>>N>>M && (N||M))
	{
		cin>>S>>D;
		
		while(M--)
		{
			cin>>U>>V>>P;
			adj[U].push_back(make_pair(P,V));
		}
		
        // almost_shotest() 한 번 실행해서 값 할당해주며 eraseEdge();
		eraseEdge(D, almost_shotest(N, S));
		
        // eraseEdge 를 통해 최단 경로 다 지웠으니 다시 almost_shotest();
        // Parent 가 섞여서 의미 없어지지만 어차피 사용하지 않을테니 상관 없다.
		int ans = almost_shotest(N, S);
		
		if(ans != INF)
			cout<<ans<<'\n';
		else
			cout<<"-1\n";
		
        // 다음 테스트 케이스를 위해 초기화.
		for(int i=0; i<N; ++i)
		{
			adj[i].clear();
			
			while(!Parent[i].empty())
				Parent[i].pop();
		}
	}
}

 

 

테스트 케이스

---

1)
2 1
0 1
0 1 3
0 0

ans 1)
-1

2)
3 3
0 2
0 1 2
0 2 1
1 2 3
0 0

ans 2)
5

3)
4 5
0 2
0 1 5
0 3 1
1 2 1
3 1 1
3 2 2
0 0

ans 3)
-1

TC 1 은 잘 지우는 지 확인하기 위해 시도해봤고, TC 2는 거의 최단 경로를 잘 인식하는지 확인하려고 시도했다. TC 3의 경우 질문 게시글에서 테스트 케이스 확인하다가 여러 최단 경로를 한 번에 잘 삭제하는지 확인하기 위해 시도해봤다.

 

 

결과

---

시간 초과는 꼭 필요하지 않은 곳에서도 almost_shotest 를 호출해서 나온 것 같고, 틀렸습니다는 여러 최단 경로를 한 번에 삭제하지 않아서 나왔다.