[백준 5214번] 환승

난이도: 골드 I

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

5214번: 환승

 

백준 5214번 문제 환승

 

각 노드와 연결 정보가 주어지고, 시작점으로부터 도착점까지 최단 거리를 구하면 되는 문제입니다.

단순하게 접근했다가 틀렸는데, 문제의 조건을 분석해 봅시다.

 

한 튜브에 최대 1000개의 역이 연결되어 있고, 튜브는 최대 1000개 존재합니다.

이것을 튜브에 연결된 모든 역이 서로 연결되어 있는 방식으로 구현하면, O(n^3)의 공간복잡도를 가지게 되어 메모리 초과에 걸립니다.

메모리 초과에 걸린 코드:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 1e9

int n, k, m;
int visited[100001];

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k >> m;

	vector<vector<int> > graph(n + 1);;
	for (int i = 0; i < m; i++) {
		vector<int> temp;
		for (int j = 0; j < k; j++) {
			int input;
			cin >> input;
			temp.push_back(input);
		}
		for (int a = 0; a < temp.size() - 1; a++) {
			for (int b = a + 1; b < temp.size(); b++) {
				graph[temp[a]].push_back(temp[b]);
				graph[temp[b]].push_back(temp[a]);
			}
		}
	}

	for (int i = 2; i <= n; i++) {
		visited[i] = INF;
	}
	visited[1] = 1;

	queue<int> q;
	q.push(1);

	while (!q.empty()) {
		int c = q.front();
		q.pop();

		for (int i = 0; i < graph[c].size(); i++) {
			if (visited[graph[c][i]] > visited[c] + 1) {
				visited[graph[c][i]] = visited[c] + 1;
				q.push(graph[c][i]);
			}
		}
	}

	cout << visited[n];
	return 0;
}

 

따라서 저는 다른 방법을 고민해 보았습니다.

모든 노드는 각자 튜브에 연결되어 있으므로, 각 튜브마다 가상의 역을 만들면 어떨까요?

같은 튜브에 연결된 두 역 A와 B가, A -> B로 바로 연결되는 것이 아닌 A -> Tube -> B와 같은 방법으로 연결되는 것입니다.

튜브는 최대 1000개이므로, 기존의 크기 100001의 방문 배열에 1000을 추가하여 크기 101001의 배열만을 사용하면 됩니다.

 

 

 

실제로 각 노드 사이를 이동할 때 기록되는 거리가 +2가 되고, 시작점을 이미 1로 간주하므로,

정답을 출력할 때는 visited[n]/2 + 1을 출력하였습니다.

 

채점 결과

 

맨 처음에는 위의 메모리 초과에 걸리는 코드를 제출했고, 두 번째 제출할 때는 도달하지 못하는 경우를 고려하지 않았습니다.

전부 해결하니 수월하게 풀리네요.