백준 5214 : 환승

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

5214번: 환승

 

이 문제는 그냥 단순히 bfs를 통한 그래프 탐색으로 해결할 수 있는 문제처럼 보인다. 다만, 문제 해결 로직은 간단하지만, edge를 저장하는 방식에서 일반적인 방법을 사용할 시 겹치는 데이터가 매우 많아 메모리 초과를 만나게 된다.

 

그에 대한 해결책으로 하이퍼 튜브 자체를 하나의 노드로 보는 방법을 사용했다. 이 방법에 대한 설명은 아래 블로그에 그림과 함께 상세히 설명되어있다.

https://yabmoons.tistory.com/260

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

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using pii = pair<int, int>;

int n, k;
vector<int> edge[101'001]; //(1 ~ n) -> node, (n + 1) ~ (n + m) -> hypertube
bool visited[101'001];

int bfs() {
	int cur, cur_dist, npos, n_dist;
	queue<pii> q;
	q.emplace(1, 1);
	visited[1] = 1;

	while (!q.empty()) {
		cur = q.front().first;
		cur_dist = q.front().second;
		q.pop();
		
		if (cur == n) return cur_dist;

		for (int i = 0; i < edge[cur].size(); i++) {
			npos = edge[cur][i];
			if (visited[npos]) continue;

			n_dist = cur_dist + 1;
            //다음 노드가 하이퍼튜브일 경우 갯수 증가 X
			if (npos > n) n_dist--;

			q.emplace(npos, n_dist);
			visited[npos] = 1;
		}
	}

	return -1;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int m, tmp;
	cin >> n >> k >> m;

	for (int j = 1; j <= m; j++) {
		for (int i = 0; i < k; i++) {
			cin >> tmp;
			edge[n + j].push_back(tmp);
			edge[tmp].push_back(n + j);
		}
	}

	cout << bfs();
	return 0;
}

메모리: 17308 kb

시간: 256 ms