[백준] 9370 미확인 도착지

⋆｡♡ﾟ☁︎ ⋆｡선주 ﾟ☁︎ ﾟ｡♡⋆｡·2023년 2월 28일

목록 보기

270/271

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

틀린 풀이 1

다익스트라 알고리즘 사용 풀이
최단 경로가 여러 개가 나오는 경우 g,h를 지나는 최단경로가 존재하더라도 dijkstra에서 그걸 놓칠 수 있다
반례

input
1
5 5 2
1 2 3
1 4 3
4 5 3
1 2 2
2 3 2
3 5 2
3
5
output: 3
answer: 3 5

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

const int MAX_COST = 987654321;
const int MAX_V = 2000;

int V;
//<u, <v, w>>
vector <pair<int, int>> adj[MAX_V];

//시작 지점에서 각 지점까지의 최소 비용
vector<int> dist(MAX_V, MAX_COST);

//냄새를 맡은 도로(도로의 시작과 끝 정점 저장)
pair<int, int> smellRoad;
//목적지 후보
vector<int> cand;

void priority_queue_dijkstra(int start) {

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	dist[start] = 0;

	//최단 경로 저장
	//curNode까지 가는 최단 경로는 curNode 직전에 prevNode를 방문한다
	//route[curNode] = prevNode
	vector<int> route(V,-1);

	while (!pq.empty()) {
		int curNode = pq.top().second;
		int curW = -pq.top().first;
		pq.pop();

		for (int i = 0; i < adj[curNode].size(); i++) {
			int nextNode = adj[curNode][i].first;
			int& nextW = adj[curNode][i].second;

			if (dist[nextNode] > curW + nextW) {
				dist[nextNode] = curW + nextW;
				route[nextNode] = curNode;
				pq.push({ -dist[nextNode], nextNode });
			}
		}
	}

	//목적지 후보 중 불가능한 경우를 제외한 목록
	vector<int> possibleCand;

	//start -> dest까지 가는 최단 경로 
	for (int i = 0; i < cand.size(); ++i) {
		int dest = cand[i];
		//if (start == dest) continue; 목적지 출발지와 같은 경우 없음

		int curNode = dest;
		vector<int> destRoute; 
		destRoute.push_back(curNode);
		while (curNode != start) {
			curNode = route[curNode];
			destRoute.push_back(curNode);
		}
		reverse(destRoute.begin(), destRoute.end());

		//경로에 냄새 맡은 도로가 있는 경우 가능한 목적지
		bool possible = false;
		for (int j = 0; j < destRoute.size() - 1; ++j) {
			int u = destRoute[j];
			int v = destRoute[j + 1];
			if ((u == smellRoad.first && v == smellRoad.second) || (v == smellRoad.first && u == smellRoad.second)) {
				possible = true;
				break;
			}
		}
		if (possible) possibleCand.push_back(dest);
	}
	
	sort(possibleCand.begin(), possibleCand.end());
	for (int i = 0; i < possibleCand.size(); ++i) {
		cout << possibleCand[i]+1 << " ";
	}
	cout << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T;
	cin >> T;
	while (T--) {
		//초기화
		for (int i = 0; i < MAX_V; ++i) {
			adj[i].clear();
			dist[i] = MAX_COST;
		}
		cand.clear();

		int n, m; //정점 개수, 도로 개수
		int t; //목적지 후보 개수
		cin >> n >> m >> t;
		V = n;

		int s; //출발지
		int g, h; //냄새맡은 도로
		cin >> s >> g >> h;
		s--; g--; h--;
		smellRoad = { g, h };
		
		//간선 입력받기
		for (int i = 0; i < m; ++i) {
			int u, v, w;
			cin >> u >> v >> w;
			u--;
			v--;

			//양방향 도로
			//두 정점 사이 도로 최대 한 개

			adj[u].push_back({ v, w });
			adj[v].push_back({ u, w });
		}

		for (int i = 0; i < t; ++i) {
			int x;
			cin >> x;
			x--;
			cand.push_back(x);
		}

		priority_queue_dijkstra(s);
	}
	return 0;
}

틀린 풀이 2

플로이드-와샬 알고리즘 사용 풀이
시간 초과
- 플로이드 와샬 알고리즘 시간 복잡도 O(N^3)임에 주의하자!

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

const int MAX_COST = 987654321;
const int MAX_V = 2000;

int V;

//adj[u][v]: u -> v로 가는 최소 비용
//u와 v사이 도로 없는 경우 비용 MAX_COST
int adj[MAX_V][MAX_V];


//플로이드-와샬 알고리즘
void floyd() {
	for (int i = 0; i < V; ++i) {
		adj[i][i] = 0;
	}

	//i지점 -> j지점으로 이동할 때 거쳐가는 지점 k
	for (int k = 0; k < V; ++k) {
		for (int i = 0; i < V; ++i) {
			for (int j = 0; j < V; ++j) {
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T;
	cin >> T;
	while (T--) {
		//그래프 초기화
		for (int i = 0; i < MAX_V; ++i) {
			for (int j = 0; j < MAX_V; ++j) {
				adj[i][j] = MAX_COST;
			}
		}

		cin >> V; //정점 개수

		int m, t; //도로 개수, 목적지 후보 개수
		cin >> m >> t;

		int s; //출발지점
		cin >> s;
		s--;

		int g, h; //냄새맡은 도로
		cin >> g >> h;
		 g--; h--;
		
		//간선 입력받기
		for (int i = 0; i < m; ++i) {
			int u, v, w;
			cin >> u >> v >> w;
			u--;
			v--;

			//양방향 도로
			//두 정점 사이 도로 최대 한 개
			adj[u][v] = w;
			adj[v][u] = w;
		}

		floyd();

		//출발지에서 목적지 후보까지
		//g <-> h 도로를 통해서 최단 경로로 갈 수 있는지 확인

		vector<int> answer; //가능한 후보
		for (int i = 0; i < t; ++i) {
			int x; //목적지 후보
			cin >> x; 
			x--;

			if (adj[s][x] == (adj[s][g] + adj[g][h] + adj[h][x]))
				answer.push_back(x);
			else if(adj[s][x] == (adj[s][h] + adj[h][g] + adj[g][x]))
				answer.push_back(x);
		}
		sort(answer.begin(), answer.end());

		for (int i = 0; i < answer.size(); ++i) {
			cout << answer[i]+1 << " ";
		}
		cout << "\n";

	}
	return 0;
}

풀이

다시 다익스트라 알고리즘을 사용하여 풀이

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

const int MAX_COST = 987654321;
const int MAX_V = 2000;

int V;
//<u, <v, w>>
vector <pair<int, int>> adj[MAX_V];

int s, g, h;
//s에서 각 지점까지의 최소 비용
vector<int> distS(MAX_V, MAX_COST);
//g에서 각 지점까지의 최소 비용
vector<int> distG(MAX_V, MAX_COST);
//h에서 각 지점까지의 최소 비용
vector<int> distH(MAX_V, MAX_COST);

void priority_queue_dijkstra_s() {

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, s));
	distS[s] = 0;

	while (!pq.empty()) {
		int curNode = pq.top().second;
		int curW = -pq.top().first;
		pq.pop();

		for (int i = 0; i < adj[curNode].size(); i++) {
			int nextNode = adj[curNode][i].first;
			int& nextW = adj[curNode][i].second;

			if (distS[nextNode] > curW + nextW) {
				distS[nextNode] = curW + nextW;
				pq.push({ -distS[nextNode], nextNode });
			}
		}
	}
}
void priority_queue_dijkstra_g() {

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, g));
	distG[g] = 0;

	while (!pq.empty()) {
		int curNode = pq.top().second;
		int curW = -pq.top().first;
		pq.pop();

		for (int i = 0; i < adj[curNode].size(); i++) {
			int nextNode = adj[curNode][i].first;
			int& nextW = adj[curNode][i].second;

			if (distG[nextNode] > curW + nextW) {
				distG[nextNode] = curW + nextW;
				pq.push({ -distG[nextNode], nextNode });
			}
		}
	}
}

void priority_queue_dijkstra_h() {

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, h));
	distH[h] = 0;

	while (!pq.empty()) {
		int curNode = pq.top().second;
		int curW = -pq.top().first;
		pq.pop();

		for (int i = 0; i < adj[curNode].size(); i++) {
			int nextNode = adj[curNode][i].first;
			int& nextW = adj[curNode][i].second;

			if (distH[nextNode] > curW + nextW) {
				distH[nextNode] = curW + nextW;
				pq.push({ -distH[nextNode], nextNode });
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T;
	cin >> T;
	while (T--) {
		//초기화
		for (int i = 0; i < MAX_V; ++i) {
			adj[i].clear();
			distS[i] = MAX_COST;
			distG[i] = MAX_COST;
			distH[i] = MAX_COST;
		}

		int n, m; //정점 개수, 도로 개수
		int t; //목적지 후보 개수
		cin >> n >> m >> t;
		V = n;

		cin >> s >> g >> h;
		s--; g--; h--;

		//간선 입력받기
		for (int i = 0; i < m; ++i) {
			int u, v, w;
			cin >> u >> v >> w;
			u--;
			v--;

			//양방향 도로
			//두 정점 사이 도로 최대 한 개
			adj[u].push_back({ v, w });
			adj[v].push_back({ u, w });
		}

		priority_queue_dijkstra_s();
		priority_queue_dijkstra_g();
		priority_queue_dijkstra_h();

		//목적지 후보 중 불가능한 경우를 제외한 목록
		vector<int> answer;
		for (int i = 0; i < t; ++i) {
			int x;
			cin >> x;
			x--;

			bool possible = false;
			if ((distS[x] == (distS[g] + distG[h] + distH[x]))
				||(distS[x] == (distS[h] + distH[g] + distG[x]))) possible = true;
			
			if (possible) answer.push_back(x);
		}
		sort(answer.begin(), answer.end());
		for (int i = 0; i < answer.size(); ++i) {
			cout << answer[i] + 1 << " ";
		}
		cout << "\n";
	}
	return 0;
}

📌참고자료

경로 추적에 대하여 (다익스트라, 플로이드, )
⭐다익스트라 알고리즘에서 최단 경로 출력하기

int V;
//<u, <v, w>>
vector <pair<int, int>> adj[MAX_V];

//시작 지점에서 각 지점까지의 최소 비용
vector<int> dist(MAX_V, MAX_COST);

void priority_queue_dijkstra(int start) {

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	dist[start] = 0;

	//최단 경로 저장
	//curNode까지 가는 최단 경로는 curNode 직전에 prevNode를 방문한다
	//route[curNode] = prevNode
	vector<int> route(V, -1);

	while (!pq.empty()) {
		int curNode = pq.top().second;
		int curW = -pq.top().first;
		pq.pop();

		for (int i = 0; i < adj[curNode].size(); i++) {
			int nextNode = adj[curNode][i].first;
			int& nextW = adj[curNode][i].second;

			if (dist[nextNode] > curW + nextW) {
				dist[nextNode] = curW + nextW;
				route[nextNode] = curNode;
				pq.push({ -dist[nextNode], nextNode });
			}
		}
	}

	//start -> dest까지 가는 최단 경로 출력
	for (int dest = 0; dest < V; ++dest) {
		if (start == dest) continue;

		int curNode = dest;
		vector<int> destRoute;
		destRoute.push_back(curNode);
		while (curNode != start) {
			curNode = route[curNode];
			destRoute.push_back(curNode);
		}
		reverse(destRoute.begin(), destRoute.end());

		for (int i = 0; i < destRoute.size(); ++i) {
			cout << destRoute[i] << " ";
		}
		cout << "\n";
	}
}

⋆｡♡ﾟ☁︎ ⋆｡선주 ﾟ☁︎ ﾟ｡♡⋆｡

Be able to be vulnerable, in search of truth

이전 포스트

[백준] 1753 최단경로

다음 포스트

[백준] 9370 미확인 도착지

백준

틀린 풀이 1

틀린 풀이 2

풀이

📌참고자료

[백준] 1753 최단경로

[백준] 1238 파티

0개의 댓글