중급반 6주차 풀이 - 최단경로 (BFS, 다익스트라)

1. [1753] 최단경로 (Gold V)

다익스트라를 그대로 구현해주면 됩니다.

 

지금까지 봐왔던 문제와는 달리 "방향그래프", 즉 간선이 \( v \rightarrow w \)임에 주의하세요.

const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<pl2> adj[20020];
priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
ll dis[20020];

void Main(){
	int n, m, st; cin >> n >> m >> st;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x});
	}
	memset(dis, 0x3f, sizeof(dis));
	pq.push({0, st}); dis[st] = 0;
	while (!pq.empty()){
		int now = pq.top().sc; ll dst = pq.top().fr;
		pq.pop();
		if (dst != dis[now]){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[nxt] <= dst+d){ continue; }
			pq.push({dst+d, nxt}); dis[nxt] = dst+d;
		}
	}
	for (int i = 1; i <= n; i++){
		if (dis[i] == INF){ cout << "INF"; } else{ cout << dis[i]; }
		cout << endl;
	}
}

2. [1238] 파티 (Gold III)

\( X \Rightarrow v \)는 그냥 다익스트라 1번 돌려주면 다 구해집니다.

하지만 \( v \Rightarrow X \)는 어떻게 구할까요?

 

\( N \le 1\;000 \)이라 이론상 다익스트라를 \( N \)번 돌릴 수도 있겠지만, 훨씬 편한 풀이가 존재합니다.

\( v \Rightarrow X \)는 \( X \Leftarrow v \)이므로, "그래프의 간선 방향을 뒤집어주면" \( X \Rightarrow v \)가 됩니다!

 

즉, 아래와 같은 방식으로 풀 수 있습니다.

• 원래 방향대로 그래프 \( G_{0} \)를 만들고, 간선의 방향이 반대인 그래프 \( G_{1} \)을 만든다.
• 두 그래프에서 다익스트라를 돌려 시작점 \( X \)에서의 거리 \( D_{0, v}, D_{1, v} \)를 구한다.
• \( \max_{1 \ge v \ge N} (D_{0, v} + D_{1, v}) \)를 구한다.

+ 그래프가 2종류 이상일 때는 이렇게 앞부분의 인덱스를 바꿔가면서 다익스트라를 돌려주면 되고,

다익스트라 함수를 만들면 앞부분의 인덱스를 바꾸기가 편해집니다.

const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<pl2> adj[2][1020];
ll dis[2][1020];

void djk(int idx, int st){
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, st}); dis[idx][st] = 0;
	while (!pq.empty()){
		int now = pq.top().sc; ll dst = pq.top().fr;
		pq.pop();
		if (dst != dis[idx][now]){ continue; }
		for (pl2 p : adj[idx][now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[idx][nxt] <= dst+d){ continue; }
			pq.push({dst+d, nxt}); dis[idx][nxt] = dst+d;
		}
	}
}

void Main(){
	int n, m, st; cin >> n >> m >> st;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[0][v].push_back({w, x}); adj[1][w].push_back({v, x});
	}
	memset(dis, 0x3f, sizeof(dis));
	djk(0, st); djk(1, st);
	ll ans = 0;
	for (int i = 1; i <= n; i++){ ans = max(ans, dis[0][i] + dis[1][i]); }
	cout << ans;
}

3. [1504] 특정한 최단 경로 (Gold IV)

\( 1 \)에서 \( v, w \)를 거쳐 \( N \)로 가는 최단경로는 아래 두 경우 중 하나가 됩니다.

• \( 1 \Rightarrow v \Rightarrow w \Rightarrow N \)
• \( 1 \Rightarrow w \Rightarrow v \Rightarrow N \)

그러니, \( 1, v, w \)에서 각각 다익스트라를 돌려준 뒤, \( \min(D_{s,v} + D_{v,w} + D_{w,e}, D_{s,w} + D_{w,v} + D_{v,e} \)를 구해주면 됩니다.

const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<pl2> adj[820];
ll dis[3][820];

void djk(int idx, int st){
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, st}); dis[idx][st] = 0;
	while (!pq.empty()){
		int now = pq.top().sc; ll dst = pq.top().fr;
		pq.pop();
		if (dst != dis[idx][now]){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[idx][nxt] <= dst+d){ continue; }
			pq.push({dst+d, nxt}); dis[idx][nxt] = dst+d;
		}
	}
}

void Main(){
	int n, m; cin >> n >> m;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	int v, w; cin >> v >> w;
	memset(dis, 0x3f, sizeof(dis));
	djk(0, 1); djk(1, v); djk(2, w);
	if (dis[0][v] == INF || dis[1][w] == INF || dis[2][n] == INF){ cout << -1; return; }
	ll r1 = dis[0][v] + dis[1][w] + dis[2][n];
	ll r2 = dis[0][w] + dis[2][v] + dis[1][n];
	cout << min(r1, r2);
}

4. [18352] 특정 거리의 도시 찾기 (Silver II)

가중치가 없기 때문에, BFS를 한 번 돌려주면 모든 정점까지의 최단경로를 구할 수 있습니다.

그러니, 최단경로를 다 구해주고 \( D_{v} = K \)인 정점의 개수를 세주면 됩니다.

vector<int> adj[300020];
int dis[300020];

void bfs(int st){
	queue<pi2> q; q.push({st, 0}); dis[st] = 0;
	while (!q.empty()){
		int now = q.front().fr, dst = q.front().sc;
		q.pop();
		for (int nxt : adj[now]){
			if (dis[nxt] != -1){ continue; }
			q.push({nxt, dst+1}); dis[nxt] = dst+1;
		}
	}
}

void Main(){
	int n, m, k, st; cin >> n >> m >> k >> st;
	while (m--){
		int v, w; cin >> v >> w;
		adj[v].push_back(w);
	}
	memset(dis, -1, sizeof(dis));
	bfs(st);
	bool ans = 0;
	for (int i = 1; i <= n; i++){
		if (dis[i] == k){ ans = 1; cout << i << endl; }
	}
	if (!ans){ cout << -1; }
}

5. [1927] 최소 힙 (Silver II)

STL priority_queue 연습 문제입니다.

pq.push(x); pq.top(); pq.pop();을 할 수 있으면 됩니다.

priority_queue< int, vector<int>, greater<int> > pq;

void Main(){
	int q; cin >> q;
	while (q--){
		int x; cin >> x;
		if (x > 0){ pq.push(x); }
		if (x == 0){
			if (pq.empty()){ cout << 0 << endl; }
			else{ cout << pq.top() << endl; pq.pop(); }
		}
	}
}

6. [17396] 백도어 (Gold V)

특정 정점(들)을 지날 수 없는 다익스트라 문제입니다.

이는 간단히 해결할 수 있는데, \( v \)번 정점을 지날 수 없다면 \( v \)번 정점과 연결된 모든 간선들을 다 무시해주면 됩니다.

 

이제 남은 간선들로 아무 일 없다는 듯이 다익스트라를 신나게 돌려주면 됩니다.

const ll INF = 0x3f3f3f3f3f3f3f3f;

bool chk[100020];
vector<pl2> adj[100020];
ll dis[100020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++){ cin >> chk[i]; } chk[n-1] = 0;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	memset(dis, 0x3f, sizeof(dis)); dis[0] = 0;
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq; pq.push({0, 0});
	while (!pq.empty()){
		int now = pq.top().sc; ll dst = pq.top().fr;
		pq.pop();
		if (dis[now] != dst){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (chk[nxt]){ continue; }
			if (dis[nxt] <= dst+d){ continue; }
			pq.push({dst+d, nxt}); dis[nxt] = dst+d;
		}
	}
	if (dis[n-1] == INF){ cout << -1; } else{ cout << dis[n-1]; }
}

7. [1719] 택배 (Gold IV)

일단 최단경로를 구해야 하니, 다익스트라를 써봅시다.

그런데, "최단경로"의 첫 번째 정점은 어떻게 알아낼까요?

 

만약 최단경로의 거리가 1이라면, 나 자신이 1번 정점이 됩니다.

그렇지 않다면, "나까지 오는 경로"에서의 1번 정점이 최단경로의 1번 정점이 됩니다.

이를 저장해주면서 구현해주면 됩니다.

 

\( DIS_{v, w} := \) \( v \Rightarrow w \)의 최단 거리

\( PRE_{v, w} := \) \( v \Rightarrow w \)의 최단경로에 있는 첫 번째 정점

const int INF = 0x3f3f3f3f;

vector<pi2> adj[220];
int dis[220][220], pre[220][220];

void djk(int st){
	priority_queue< pi2, vector<pi2>, greater<pi2> > pq; pq.push({0, st});
	dis[st][st] = 0;
	while (!pq.empty()){
		int now = pq.top().sc, dst = pq.top().fr;
		pq.pop();
		if (dis[st][now] != dst){ continue; }
		for (pi2 p : adj[now]){
			int nxt = p.fr, d = p.sc;
			if (dis[st][nxt] <= dst+d){ continue; }
			//cout << "VTX " << st << " -> " << nxt << endl;
			pq.push({dst+d, nxt}); dis[st][nxt] = dst+d;
			pre[st][nxt] = (now==st ? nxt : pre[st][now]);
		}
	}
}

void Main(){
	int n, m; cin >> n >> m;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	memset(dis, 0x3f, sizeof(dis));
	for (int st = 1; st <= n; st++){ djk(st); }
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (i==j){ cout << '-'; } else{ cout << pre[i][j]; }
			cout << ' ';
		}
		cout << endl;
	}
}

8. [1162] 도로포장 (Gold I)

일단 내가 갈 경로를 지정하면, 그 경로 밖에 있는 도로는 포장해서 얻는 이익이 없습니다.

그러니, 지금까지 온 경로에서 포장한 도로의 개수를 추가적으로 저장해봅시다.

\( DIS_{k, v} := \) \( k \)개의 도로를 포장해서 \( v \)까지 오는 최단 거리

 

이렇게 정의하면 간선은 아래와 같이 2종류가 됩니다.

• 포장하지 않은 도로: \( (v,k) \xrightarrow{x} (w,k) \)가 됩니다.
• 포장한 도로: \( (v,k) \xrightarrow{0} (w, k-1) \)가 됩니다.

정점이랑 간선이 다 만들어졌으니 다익스트라로 최단경로를 찾아주면 됩니다.

const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<pl2> adj[10020];
ll dis[21][10020];

void djk(int st, int k){
	priority_queue< pl3, vector<pl3>, greater<pl3> > pq;
	pq.push({ 0, {st, k} }); dis[k][st] = 0;
	while (!pq.empty()){
		int now = pq.top().sc.fr, cnt = pq.top().sc.sc;
		ll dst = pq.top().fr; pq.pop();
		//cout << "PQ " << now << ' ' << cnt << " = " << dst << endl;
		if (dst != dis[cnt][now]){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[cnt][nxt] > dst+d){
				pq.push({ dst+d, {nxt, cnt} }); dis[cnt][nxt] = dst+d;
			}
			if (cnt > 0 && dis[cnt-1][nxt] > dst){
				pq.push({ dst, {nxt, cnt-1} }); dis[cnt-1][nxt] = dst;
			}
		}
	}
}

void Main(){
	int n, m, k; cin >> n >> m >> k;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	memset(dis, 0x3f, sizeof(dis));
	djk(1, k);
	ll ans = INF;
	for (int i = 0; i <= k; i++){ ans = min(ans, dis[i][n]); }
	cout << ans;
}

9. [5719] 거의 최단 경로 (Platinum V)

최단경로의 거리를 \( X \)라고 부릅시다.

그럼 어떤 간선 \( v \xrightarrow{x} w \)가 최단경로에 포함된다는 건 무슨 의미일까요?

 

\( s \Rightarrow v \)의 거리를 \( a \), \( w \Rightarrow e \)의 거리를 \( b \)라고 할 때

\( a + x + b = X \)이면 \( v \xrightarrow{x} w \)가 최단경로에 포함되는 간선임은 자명합니다.

또한, \( v \xrightarrow{x} w \)가 최단경로에 포함되는 간선이라면 \( a + x + b = X \)인 \( a, b \)가 적어도 하나 이상 존재해야 합니다.

 

그러므로, \( s \Rightarrow v \)와 \( w \Rightarrow e \)의 거리를 미리 구해둔 뒤,

\( X - (a+b) = x \)인 간선들을 무시해주면서 다익스트라를 돌려주면 됩니다.

const ll INF = 1e15;
int n, m;
vector<pl2> adj[2][520];
ll dis[2][520], res[520];

void f(int st, int idx){
	for (int i = 0; i < n; i++){ dis[idx][i] = INF; }
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, st}); dis[idx][st] = 0;
	while (!pq.empty()){
		ll dst = pq.top().fr; int now = pq.top().sc;
		pq.pop();
		if (dst != dis[idx][now]){ continue; }
		for (pl2 p : adj[idx][now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[idx][nxt] <= d+dst){ continue; }
			dis[idx][nxt] = d+dst;
			pq.push({dis[idx][nxt], nxt});
		}
	}
}

void Main(){
	while (1){
		cin >> n >> m;
		if (n == 0 && m == 0){ return; }
		int st, ed; cin >> st >> ed;
		while (m--){
			int a, b, c; cin >> a >> b >> c;
			adj[0][a].push_back({b, c}); adj[1][b].push_back({a, c});
		}
		f(st, 0); f(ed, 1);
		for (int i = 0; i < n; i++){ res[i] = INF; }
		priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
		pq.push({0, st}); res[st] = 0;
		while (!pq.empty()){
			ll dst = pq.top().fr; int now = pq.top().sc;
			pq.pop();
			if (dst != res[now]){ continue; }
			for (pl2 p : adj[0][now]){
				int nxt = p.fr; ll d = p.sc;
				if (dis[0][now] + d + dis[1][nxt] == dis[0][ed]){ continue; }
				if (res[nxt] <= d+dst){ continue; }
				res[nxt] = d+dst;
				pq.push({res[nxt], nxt});
			}
		}
		if (res[ed] == INF){ cout << -1; } else{ cout << res[ed]; }
		cout << endl;
		for (int i = 0; i < n; i++){ adj[0][i].clear(); adj[1][i].clear(); }
	}
}

10. [1854] K번째 최단경로 찾기 (Platinum IV)

풀이가 간단하면서 무서운데, 1번째 최단경로부터 K번째 최단경로까지 다 저장하면서 다익스트라를 돌려주면 됩니다.

이 때 최단경로를 저장하는 방법은 각 정점별로 최대 힙을 두는 방식으로 해결할 수 있으며,

최대 힙에 새로운 경로를 넣은 뒤, 힙의 크기가 K를 넘으면 거리가 가장 큰 경로를 빼내면서 다익스트라를 돌려주면 됩니다.

 

새로운 경로가 최대 힙에 들어갈 수 없다면, 그 새로운 경로는 더 이상 탐색하지 않는 방식으로 짜야 무한 반복을 피할 수 있습니다.

 

+ 이래도 잘 도는 이유가, 각 정점은 최대 100회 check되기 때문에 (= now에 최대 100번 들어가기 때문에) 시간복잡도가 보장됩니다.

정확히는, 100번 넘게 들어갈 수는 있지만 K회 넘게 들어가는 시점부터는 최단경로의 가능성이 없어지므로 간선 탐색을 하지 않게 되고, 이로 인해 시간복잡도에 영향을 끼치지 않게 됩니다.

const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<pl2> adj[10020];
priority_queue<ll> dis[10020];
int cnt[10020];

void djk(int st, int k){
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, 1}); dis[st].push(0);
	//cout << "HUH" << endl << flush;
	while (!pq.empty()){
		int now = pq.top().sc; ll dst = pq.top().fr;
		//cout << "PQ " << now << ' ' << cnt[now] << " = " << dst << endl << flush;
		pq.pop();
		cnt[now] += 1; if (cnt[now] > k){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[nxt].size() == k && dis[nxt].top() <= dst+d){ continue; }
			pq.push({dst+d, nxt});
			dis[nxt].push(dst+d); if (dis[nxt].size() > k){ dis[nxt].pop(); }
		}
	}
}

void Main(){
	int n, m, k; cin >> n >> m >> k;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x});
	}
	djk(1, k);
	for (int i = 1; i <= n; i++){
		if (dis[i].size() < k){ cout << -1; } else{ cout << dis[i].top(); }
		cout << endl;
	}
}