[G5] 백준 17396번 백도어 C++ 다익스트라

리뷰

 

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

문제 조건을 읽고 분명 int로 터진다는건 알고 있었지만... 실수를 해서 두번이나 틀렸다. ㅠ

 

 

전역 변수

• N : 분기점의 최대 개수를 저장할 상수 변수
• n : 분기점의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• lst : 각 분기점이 시야에 노출되는지를 저장할 정수형 배열
• Edge : 간선 정보 중 다음 노드 nn, 간선의 가중치 nt를 정의할 구조체
• edges : 인접 리스트를 저장할 Edge타입 벡터 배열
• Pos : 시뮬레이션 시 사용할 현재 노드 cn, 현재 누적 시간 ct를 정의할 구조체, ct를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

ll dijkstra()

 

다익스트라를 통해 시야를 피해 넥서스 까지 가는 최단 거리를 구하는 함수

1. Pos 타입의 우선순위 큐 pq를 초기화 하고, 초깃값 0, 0을 push해준다.
2. long long타입의 벡터 dist를 n크기로, 초기값은 300억보다 큰 값을 넣어주고, 시작 위치는 0으로 변경해 준다.
3. pq가 빌 때 까지 while 루프를 수행하고, 매 루프마다 요소를 한 개씩 꺼내어 준다.
4. 첫 번째 기저 조건으로 dist[cn]에 기록된 값이 ct보다 작을 경우 continue 처리해 준다.
5. 두 번째 기저 조건으로 cn이 n - 1인 경우 ct에 저장된 값을 리턴해 준다.
6. cn의 인접 리스트를 순회하며 nn의 lst값이 1이면서 nn이 n - 1이 아니라면 continue처리해 준다.
7. 만약 dist[nn]이 ct + nt보다 크다면 값을 갱신해 주고 pq에 nn과 ct + nt를 push해준다.
8. while 루프가 종료될 때 까지 기저 조건에 도달하지 못한 경우 -1을 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받고, n개의 시야 정보를 lst배열에 입력 받아준다.
2. m개의 간선을 입력 받고, edges에 양방향으로 간선을 추가해 준다.
3. dijkstra함수를 호출하고 받은 리턴 값을 출력해 준다.

 

트러블 슈팅

1. int 범위를 넘어설 수 있는 자료구조는 모두 long long타입으로 변환을 해주었다.
2. 다만, Pos를 파싱해 오는 과정에서 ct, nt를 int로 받은 것이 오버플로우의 영향이 있었다.
3. ct, nt를 long long 타입으로 바꿔주니 AC를 받았다. 이래서 습관이 중요한 것 같다.

 

참고 사항

• 간선이 30만개에 간선의 가중치가 10만으로 dist벡터의 초기값은 30만 * 10만보다 크게 설정해야 한다.

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>
#define ll long long
using namespace std;

const int N = 100000;
int n, m;
int lst[N];
struct Edge {
	int nn;
	ll nt;
};
vector<Edge> edges[N];
struct Pos {
	int cn;
	ll ct;
	bool operator<(const Pos& other) const {
		return ct > other.ct;
	}
};

ll dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0 });
	vector<ll> dist(n, 1e15);
	dist[0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn;
		ll ct = pos.ct;
		if (dist[cn] < ct) continue;
		if (cn == n - 1) return ct;
		
		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn;
			ll nt = edge.nt;
			if (lst[nn] && nn != n - 1) continue;
			if (dist[nn] > ct + nt) {
				dist[nn] = ct + nt;
				pq.push({ nn, ct + nt });
			}
		}
	}
	return -1;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> lst[i];

	while (m--) {
		int a, b;
		ll c;
		cin >> a >> b >> c;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	cout << dijkstra();
}