[G3] 백준 1939번 중량제한 C++ 다익스트라, 우선순위 큐, 최단 경로

리뷰

 

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

다익스트라를 사용하긴 하는데 최소값이 아닌 최대값을 구하는 문제

 

 

전역 변수

• n : 주어지는 섬의 개수를 저장할 변수
• m : 주어지는 다리의 개수를 저장할 변수
• v : 섬에 방문처리를 하기 위한 논리형 배열
• Edge : 간선의 정보, 다음 노드와 다리의 중량 제한값을 정의하기 위한 구조체
• Cur : 현재 노드와 현재까지의 최소 중량 제한 값을 정의하기 위한 구조체, 중량 제한 값을 기준으로 내림차순 정렬
• edges : Edge타입의 벡터 배열, 인접리스트를 저장하기 위한 자료 구조

 

함수

1. bfs

int bfs()

 

너비 우선 탐색을 통해 출발 섬에서 목표 섬까지의 최대 중량 제한을 구하는 함수

1. 시작 섬 번호와 도착 섬 번호를 각각 정수형 변수 sn, dn에 입력 받아준다.
2. Cur타입 우선순위 큐 pq를 초기화 하고, 시작 노드와 매우 큰 값을 push해준다.
3. 정수형 벡터 dist를 n + 1크기, 모든 값은 0으로 초기화 한다.
4. pq가 빌 때 까지 while루프를 돌며 매 루프마다 요소를 한개씩 꺼내준다.
5. 꺼낸 후 dist의 cn인덱스를, 현재 까지의 중량 제한의 최소값과 기본값 중 큰 값으로 변경해 준다.
6. 만약 cn이 dn에 도달하였으면 break처리를 해준다.
7. 만약 방문 처리가 된 섬이라면 continue처리를 해준다.
8. 기저 조건에 해당하지 않는다면 방문처리 후 인접 리스트를 순회한다.
9. 다음 노드 nn과, 현재까지의 최소 중량과 nn에 연결된 다리의 중량 중 작은 값을 nw에 저장해 준다.
10. pq에 nn과 nw를 push해준다.
11. while루프가 종료된 후 dist의 dn인덱스에 저장된 값을 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받고, m번의 반복문을 수행해 준다.
2. m개의 간선 정보를 edges배열에 양방향으로 추가해 준다.
3. bfs함수를 호출하고 받은 리턴 값을 출력해 준다.

 

트러블 슈팅

1. 방문 처리를 진행하지 않은 경우 메모리 초과가 출력되었다.
2. for문 안에서 최대값 갱신, 가지 치기를 하니 최적해가 출력되지 않았다.

 

참고 사항

• 약간 우선순위 큐를 사용하여 그리디하게 문제를 접목하는 문제라고 생각된다.
• 방문처리와 최대값 갱신의 위치가 중요했던 문제

 

정답 코드

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

int n, m;
bool v[10001];
struct Edge {
	int nn, w;
};
struct Cur {
	int cn, mw;
	bool operator<(const Cur& other) const {
		return mw < other.mw;
	}
};
vector<Edge> edges[10001];

int bfs() {
	int sn, dn; cin >> sn >> dn;
	priority_queue<Cur> pq;
	pq.push({ sn, 2000000000 });
	vector<int> dist(n + 1, 0);

	while (!pq.empty()) {
		Cur cur = pq.top(); pq.pop();
		int cn = cur.cn, mw = cur.mw;
		dist[cn] = max(dist[cn], mw);
		if (cn == dn) break;
		if (v[cn]) continue;
		v[cn] = 1;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nw = min(mw, edge.w);
			pq.push({ nn, nw });
		}
	}
	return dist[dn];
}

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

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