[백준 5214] 환승 (C++)

문제 링크: https://www.acmicpc.net/problem/5214

5214번: 환승

1. 주의할 점

- Node의 수가 많아서 2차 배열로 할 경우 메모리 초과가 발생 가능하다

- HyperTube를 어떻게 저장할 것인지 생각하자

 

2. 구현

- 1차 배열의 vector를 선언한다(1~Node : 현재 Node가 포함되어 있는 HyperTube, N+1 ~ N+query: 해당 튜브에 포함된 idx를 저장)

- 다익스트라와 비슷한 방식으로 접근 시작

- 우선순위큐를 사용해서 구현-> 240ms

- 일반 큐를 사용해서 구현-> 184ms

이미 정렬되어 있는 상태를 한번 더 정렬하기 때문에 시간차이가 난다고 개인적으로 생각한다.

 

[Queue 사용] 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct info {
	int idx, val;
};
info tmp;
vector<int> hyper[101001];		//1~n: 각 node에 포함된 hypertube정보, n+1~n+query: hypertube에 대한 정보
bool dist[101001] = { false, };
int result = -1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int node, conn, query, tt;
	cin >> node >> conn >> query;
	for (int i = 0; i < query; i++) {
		for (int j = 0; j < conn; j++) {
			cin >> tt;
			hyper[node + i + 1].push_back(tt);
			hyper[tt].push_back(node + i + 1);
		}
	}
	queue<info> q;
	tmp.idx = 1;
	tmp.val = 1;
	q.push(tmp);
	dist[1] = true;
	while (!q.empty()) {
		int cidx = q.front().idx;
		int cv = q.front().val;
		q.pop();
		if (cidx == node) {
			result = cv;
			break;
		}
		for (int i = 0; i < hyper[cidx].size(); i++) {
			int qry = hyper[cidx][i];
			if (dist[qry]) continue;
			dist[qry] = true;
			if (qry > node) {		//터널의 지점
				tmp.idx = qry;
				tmp.val = cv;
				q.push(tmp);
			}
			else {		//연결되어 있는 터널 정보
				tmp.idx = qry;
				tmp.val = cv + 1;
				q.push(tmp);
			}
		}
	}
	cout << result;
	system("pause");
	return 0;
}

 

[Priority_Queue 사용]

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct info {
	int idx, val;
};
info tmp;
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
vector<int> hyper[101001];		//1~n: 각 node에 포함된 hypertube정보, n+1~n+query: hypertube에 대한 정보
bool dist[101001] = { false, };
int result = -1;

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	int node, conn, query, tt;
	cin >> node >> conn >> query;
	for (int i = 0; i < query; i++) {
		for (int j = 0; j < conn; j++) {
			cin >> tt;
			hyper[node + i + 1].push_back(tt);
			hyper[tt].push_back(node + i + 1);
		}
	}
	priority_queue<info, vector<info>, cmp> pq;
	tmp.idx = 1;
	tmp.val = 1;
	pq.push(tmp);
	dist[1] = true;
	while (!pq.empty()) {
		int cidx = pq.top().idx;
		int cv = pq.top().val;
		pq.pop();
		if (cidx == node) {
			result = cv;
			break;
		}
		for (int i = 0; i < hyper[cidx].size(); i++) {
			int qry = hyper[cidx][i];
			if (dist[qry]) continue;
			dist[qry] = true;
			if (qry > node) {		//터널의 지점
				tmp.idx = qry;
				tmp.val = cv;
				pq.push(tmp);
			}
			else {		//연결되어 있는 터널 정보
				tmp.idx = qry;
				tmp.val = cv + 1;
				pq.push(tmp);
			}
		}
	}
	cout << result;
	return 0;
}