[백준 13911] 집 구하기

문제 링크 => https://www.acmicpc.net/problem/13911

13911번: 집 구하기

---

다익스트라 문제이다.

 

이문제를 처음에 접근 했을때의 코드를 먼저 살펴보도록 한다.

 

시간 초과한 코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
using ll = long long;
#define endl '\n'
#define INF 200000001

vector<pair<int, int>> vec[10001];
vector<int> mac, star;
int V, E, M, x, S, y;
int result = INF;
int dist[10001];
map<int, int> m;

void init() {
	for (int i = 1; i <= V; i++) {
		dist[i] = INF;
	}
}

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq;
	pq.push({ 0,start });
	dist[start] = 0;
	while (!pq.empty()) {
		int distance = -pq.top().first;
		int vertex = pq.top().second;
		pq.pop();
		if (distance > dist[vertex]) continue;
		for (int i = 0; i < vec[vertex].size(); i++) {
			int nextVertex = vec[vertex][i].first;
			int nextDistance = distance + vec[vertex][i].second;
			if (nextDistance < dist[nextVertex])
			{
				dist[nextVertex] = nextDistance;
				pq.push({ -nextDistance,nextVertex });
			}
		}
	}
	
	int minMac = INF, minStar = INF;
	for (int i = 0; i < mac.size(); i++) {
		if (dist[mac[i]] <= x) minMac = min(minMac, dist[mac[i]]);
	}

	for (int i = 0; i < star.size(); i++) {
		if (dist[star[i]] <= y) minStar = min(minStar, dist[star[i]]);
	}

	if (minMac == INF || minStar == INF) return;
	result = min(result, minMac + minStar);
	return;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		vec[u].push_back({ v,w });
		vec[v].push_back({ u,w });
	}

	cin >> M >> x;
	for (int i = 0; i < M; i++) {
		int v;
		cin >> v;
		m[v]++;
		mac.push_back(v);
	}

	cin >> S >> y;
	for (int i = 0; i < S; i++) {
		int v;
		cin >> v;
		m[v]++;
		star.push_back(v);
	}

	for (int i = 1; i <= V; i++) {
		if (m[i]) continue;
		init();
		dijkstra(i);
	}

	if (result == INF) {
		cout << -1 << endl;
	}
	else {
		cout << result << endl;
	}

	return 0;
}

 

맥도날드와 스타벅스가 아닌 집의 노드들에 대해 전부 다익스트라를 통해서 맥도날드와 스타벅스와의 거리를 조건에 맞는걸 찾도록 하는... 일명 완전 탐색 방법을 이용하여 문제를 해결했다.

 

그러나 이 문제에서 정점의 갯수가 10000개임을 고려한다면 O(N^2logN) 이므로 당연히 시간 초과가 날 수 밖에 없다.

 

따라서 이 문제를 어떻게 해야 효율적으로 해결할 수 있는지에 대해서 찾아보고 더미 노드라는것을 이용하여 다시 접근했다.

 

즉, 맥도날드 노드들을 하나로 묶을 수 있는 노드 하나와 스타벅스 노드들을 하나로 묶을 수 있는 노드 하나를 임의로 만들어서 해결한다면 다익스트라를 단 2번만 사용한다면 해결할 수 있다는 것이다.

 

따라서 더미 노드를 이용하여 맥도날드 노드들을 하나로 묶은 노드에서 집까지의 거리를 vector<int> mac_V 벡터에다가 push 하고 스타벅스 노드들을 하나로 묶은 노드에서 집까지의 거리를 vector<int> star_V 벡터에다가 push 하였다.

 

그런데 더미노드와 연결한 노드들은 양방향이 아니라 더미노드가 해당 노드를 가르키도록 하는게 핵심인거 같다. (양방향으로 하니깐 틀림)

 

마지막으로 거리들을 담은 벡터들에 대해서 조건에 맞도록 값을 추려서 출력하면 된다.

 

풀이 code

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
using ll = long long;
#define endl '\n'
#define INF 200000001

vector<pair<int, int>> vec[10003];
vector<int> mac_V, star_V;
int V, E, M, x, S, y;
int result = INF;
int dist[10003];
map<int, int> m;

void init() {
	for (int i = 1; i <= 10002; i++) {
		dist[i] = INF;
	}
}

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	dist[start] = 0;
	while (!pq.empty()) {
		int distance = -pq.top().first;
		int vertex = pq.top().second;
		pq.pop();
		if (distance > dist[vertex]) continue;
		for (int i = 0; i < vec[vertex].size(); i++) {
			int nextVertex = vec[vertex][i].first;
			int nextDistance = distance + vec[vertex][i].second;
			if (nextDistance < dist[nextVertex])
			{
				dist[nextVertex] = nextDistance;
				pq.push({ -nextDistance, nextVertex });
			}
		}
	}

	if (start == 10001) {
		for (int i = 1; i <= V; i++) {
			if (m[i]) continue;
			mac_V.push_back(dist[i]);
		}
	}
	else {
		for (int i = 1; i <= V; i++) {
			if (m[i]) continue;
			star_V.push_back(dist[i]);
		}
	}
}

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

	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		vec[u].push_back({ v,w });
		vec[v].push_back({ u,w });
	}

	cin >> M >> x;
	for (int i = 0; i < M; i++) {
		int v;
		cin >> v;
		m[v]++;
		vec[10001].push_back({ v,0 });
	}

	cin >> S >> y;
	for (int i = 0; i < S; i++) {
		int v;
		cin >> v;
		m[v]++;
		vec[10002].push_back({ v,0 });
	}
	
	init();
	dijkstra(10001);
	init();
	dijkstra(10002);

	for (int i = 0; i < mac_V.size(); i++) {
		if (mac_V[i] <= x && star_V[i] <= y) {
			result = min(result, mac_V[i] + star_V[i]);
		}
	}

	if (result == INF) {
		cout << -1 << endl;
	}
	else {
		cout << result << endl;
	}

	return 0;
}