[D6] SWEA 1795번 인수의 생일 파티 C++ 다익스트라

 

리뷰

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4xuqCqBeUDFAUx

SW Expert Academy

단방향 인접 리스트를 정방향과 역방향 리스트 두개를 만들고, 각각 다익스트라를 돌려 최적해를 구하는 문제

 

 

전역 변수

• T : 테스트 케이스의 개수를 저장할 변수
• N : 각 테스트 케이스의 노드의 개수를 저장할 변수
• M : 각 테스트 케이스의 간선 개수를 저장할 변수
• X : 각 테스트 케이스의 목표 노드를 저장할 변수
• ans : 각 테스트 케이스의 정답을 저장할 변수
• Edge : 간선의 목표 노드와 거리를 정의하기 위한 구조체
• Pos : 탐색 시 현재 노드와 현재까지의 거리를 정의하고, 거리를 오름차순 정렬하기 위한 구조체

 

함수

1. solution

void solution(const vector<vector<Edge>>& asc, const vector<vector<Edge>>& desc)

 

정방향, 역방향 인접 리스트를 순회하며 목표 노드까지의 왕복 최대거리를 구하기 위한 함수

1. dijkstra함수에 정방향 인접 리스트 asc를 매개변수로 전달해 정수형 벡터 asc_Dist를 초기화 한다.
2. dijkstra함수에 역방향 인접 리스트 desc를 매개변수로 전달해 정수형 벡터 desc_Dist를 초기화 한다.
3. 1부터 N까지의 노드를 순회하며 asc_Dist, desc_Dist의 i번 인덱스의 값을 더한다.
4. 더한 값이 ans보다 크다면 ans를 계속해서 갱신해 나간다.

---

2. dijkstra

vector<int> dijkstra(const vector<vector<Edge>>& lst)

 

시작 노드로부터 모든 노드로까지의 최단 거리를 구하는 함수

1. Pos 타입의 우선순위 큐 pq를 초기화 한다.
2. pq에 초기 시작 위치인 X와 초기 거리인 0을 push해준다.
3. 정수형 벡터 dist를 N + 1크기로, 값은 적당히 큰 값으로 초기화 해준다.
4. X의 dist값을 0으로 초기화 해준다.
5. pq가 빌 때 까지 while루프를 순회한다.
6. 매 루프마다 요소를 한개씩 꺼내어 주고 다익스트라 로직을 진행한다.
7. dist 벡터를 리턴해 준다.

 

문제풀이

1. T를 입력 받고, T번의 테스트 케이스를 수행해 준다.
2. 매 테스트 케이스 마다 N, M, X값을 입력 받아준다.
3. Edge타입의 2차원 벡터 asc, desc를 모두 N + 1크기로 초기화 해준다.
4. ans를 0으로 초기화 해준다.
5. M개의 간선 정보를 asc에는 정방향으로, desc에는 역방향으로 삽입을 해준다.
6. solution함수에 asc, desc를 매개변수로 전달하여 ans값을 최대값으로 갱신해준다.
7. 각 테스트 케이스 마다 ans에 저장된 값을 테스트 케이스의 번호에 맞게 출력해 준다.

 

트러블슈팅

1. 처음엔 모든 노드로부터 X번 노드까지의 최단 거리를 더해준 뒤 X노드에서 해당 노드까지의 거리를 더해주었다.
2. N값이 1000인데 제한 시간이 1초이므로 당연히 시간 초과가 날 것 같았다.
3. 역시 예상대로 8번 테스트 케이스 이후로 시간초과가 발생하였다.
4. 고민을 하다가 그냥 역방향 인접 리스트를 한개 더 사용해 주는 방향으로 로직을 수정하였다.
5. 시간 제한에 널널하게 AC를 받았다.

 

참고 사항

• 매 테스트 케이스마다 ans의 값을 초기화 해주어야 한다, 혹은 매개변수로, 지역변수 후 리턴값으로 뽑아내야 한다.

 

정답 코드

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

int T, N, M, X, ans;

struct Edge {
	int y, c;
};

struct Pos {
	int x, d;
	bool operator<(const Pos& other) const {
		return d > other.d;
	}
};

vector<int> dijkstra(const vector<vector<Edge>>& lst) {
	priority_queue<Pos> pq;
	pq.push({ X, 0 });
	vector<int> dist(N + 1, 2e9);
	dist[X] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cd = pos.d;
		if (dist[cx] < cd) continue;

		for (const Edge& nx : lst[cx]) {
			if (dist[nx.y] > cd + nx.c) {
				dist[nx.y] = cd + nx.c;
				pq.push({ nx.y, dist[nx.y] });
			}
		}
	}
	return dist;
}

void solution(const vector<vector<Edge>>& asc, const vector<vector<Edge>>& desc) {
	vector<int> asc_Dist = dijkstra(asc);
	vector<int> desc_Dist = dijkstra(desc);
	for (int i = 1; i <= N; ++i) {
		ans = max(ans, asc_Dist[i] + desc_Dist[i]);
	}
}

int main() {
	cin >> T;
	for (int c = 1; c <= T; ++c) {
		cin >> N >> M >> X;
		vector<vector<Edge>> asc(N + 1);
		vector<vector<Edge>> desc(N + 1);
		ans = 0;
		while (M--) {
			int x, y, c; cin >> x >> y >> c;
			asc[x].push_back({ y, c });
			desc[y].push_back({ x, c });
		}
		solution(asc, desc);
		cout << "#" << c << " " << ans << "\n";
	}
}