[C/C++] 백준 5214번 - 환승 (BFS)

 

 

<코드>

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

#define MAX 100000

int N, K, M, x;
int dist[MAX+1000+1];
vector<int> station[MAX+1000+1];
// station[1~100000] : 역
// station[100001~101000] : 하이퍼루프
queue<int> q;

int BFS()
{
	q.push(1);
	dist[1] = 1;

	while (!q.empty())
	{
		int cur = q.front(); // 현위치
		q.pop();

		if (cur == N) return dist[N]; // 목적지 도착

		for (int i = 0; i < station[cur].size(); i++)
		{
			int node = station[cur][i]; // 현위치(cur)에서 갈 수 있는 곳

			if (dist[node] == 0)
			{
				q.push(node);
				if (node > MAX) dist[node] = dist[cur]; // 갈 수 있는 곳이 하이퍼루프일때
				else dist[node] = dist[cur] + 1; // 갈 수 있는 곳이 역일때
			}
		}
	}
	return -1;
}

int main()
{
	cin >> N >> K >> M;
	for (int i = 1; i <= M; i++)
		for (int j = 1; j <= K; j++)
		{
			cin >> x;
			station[x].push_back(MAX + i);
			station[MAX + i].push_back(x);
		}
	cout << BFS() << '\n';
}

 

풀이 방법

예제의 입력 1로 예시를 들겠습니다.

 

위의 입력으로 station 벡터에 저장되는 값들은 아래와 같습니다.

station벡터의 인덱스 1~100,000까지는 역과 연결된 하이퍼루프들의 정보를 담고 있고,
station벡터의 인덱스 100,000~101,000까지는 하이퍼루프와 연결된 역들의 정보를 담고 있습니다.

예를 들어 station[1]에 저장된 100001과 100002는 1 번역과 연결된 하이퍼루프들이고,
station[100004]에 저장된 5,6,7은 하이퍼루프 1000004와 연결된 역들입니다.

역과 하이퍼루프 그래프

따라서 1 번역부터 9 번역까지의 최단거리를 BFS를 통해서 구해주면 됩니다.

 

구하는 과정을 살펴보면,

q.push(1);
	dist[1] = 1;

	while (!q.empty())
	{
		int cur = q.front(); // 현위치
		q.pop();

		if (cur == N) return dist[N]; // 목적지 도착

		for (int i = 0; i < station[cur].size(); i++)
		{
			int node = station[cur][i]; // 현위치(cur)에서 갈 수 있는 곳

			if (dist[node] == 0)
			{
				q.push(node);
				if (node > MAX) dist[node] = dist[cur]; // 갈 수 있는 곳이 하이퍼루프일때
				else dist[node] = dist[cur] + 1; // 갈 수 있는 곳이 역일때
			}
		}
	}
	return -1;

 

1. 큐에 1 번역을 push 합니다. 그런 다음 "현 위치"라는 의미의 cur변수에 저장해주고 큐를 pop 합니다.

2. for문을 돌면서 큐에 1 번역과 연결된 100001번 하이퍼루프와 100002번 하이퍼루프를 push 합니다.
( q = {100001, 100002} )

3. 다시 while문 위로 올라와서 cur변수에 큐의 front인 100001번 하이퍼루프 저장해주고 큐를 pop 합니다.

4. 그리고 100001번 하이퍼루프에서 갈 수 있는 곳들(2, 3 번역)을 push 해줍니다.
( q = {100002, 2, 3} )

5. 다시 while문 위로 올라와서 cur변수에 큐의 front인 100002번 하이퍼루프 저장해주고 큐를 pop 합니다.

6. 그리고 100002번 하이퍼루프에서 갈 수 있는 곳들(4, 5 번역)을 push 해줍니다.( q = {2, 3, 4, 5} )

.........(목적지에 도착할 때까지 계속 반복)........

 

그리고 번호들을 push 할 때마다 번호가 100,001 이상이라면 해당 번호는 하이퍼루프라는 의미이므로 dist 값을 +1 해주지 않고 100,000 이하, 즉 해당 번호가 역일 때만 dist값을 +1 해줍니다.

 

 

www.acmicpc.net/problem/5214

5214번: 환승