boj, 백준) 5214. 환승 ( C / C++ )

1. 문제 링크

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

5214번: 환승

2. 문제 개요

하이퍼 튜브 하나는 역 K를 서로 연결한다. 1 번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개인지 구하는 문제.

3. 문제 힌트!!

   각 역을 노드로 두면 시간초과. -> 그럼 노드는 튜브가 되어야 함.

 

4. 문제 풀이

하이퍼 튜브 정보를 저장하기 위해

각 노드는 몇 번째 튜브에 속해있는지, 각 하이퍼 튜브에는 어느 노드들이 들어있는지, 저장해야 한다.

저장하고, 시작점을 큐에 넣고 BFS를 시작한다. 밑 코드의 pair <int, int>는 <현재 노드 번호, 이때까지 거쳐온 노드수>이다.

 

queue에서 꺼낼 때 도착 노드면 거쳐온 노드수를 출력하고 main함수를 종료시키면 된다.

 

queue에서 꺼낸 노드는 몇 번째 튜브에 속해있는지 저장하는 벡터를 참고하여 연결된 또 다른 튜브로 이동한다.

이동한 하나의 튜브에 대해서,

튜브의 모든 노드들을 검사하는데, 이동할 튜브에서 자기 자신을 제외한 다른 노드들을 거쳐온 노드수 +1과 함께 queue에 삽입한다.

 

즉,

FOR ( cur_node와 연결된 TUBE에 대해서)

   next = 연결된 TUBE 중 1개

   dist =  현재 거리 + 1

 

   이때까지 방문하지 않은 튜브라면

       FOR( 연결된 TUBE 중 모든 NODE에 대하여)

               TUBE의 NODE가 cur_node와 같다면 거쳐간 노드수 증가 x ( Continue)

               이때까지 방문하지 않은  NODE라면 

                                 Queue에 pair <연결된 TUBE 중 NODE 중 1개, dist>를 push 하고 방문 처리함

 

이런 느낌의 순서대로 한다.  

                        

 

5. 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n, k, m;
vector<vector<int>> v;	//group 
vector<vector<int>> group;	//element
queue<pair<int,int>> q;	 //num ,count 
bool visited[1001] = { false, };
//각 노드의 방문변수를 만들어 시간을 더 줄임.
bool visitednode[100001] = { false, };

int main(void)
{
	scanf("%d %d %d", &n, &k, &m);	

	v.resize(n + 1);
	group.resize(m + 1);
	for (int i = 1; i <= m; ++i)
		for (int j = 0; j < k; ++j)
		{
			int val;
			scanf("%d", &val);
			v[val].push_back(i);
			group[i].push_back(val);
		}

	q.push(make_pair(1,1));

	while (!q.empty())
	{
		int cur = q.front().first;
		int ccount = q.front().second;
		q.pop();

		if (cur == n)
		{
			printf("%d", ccount);
			return 0;
		}

		int len = v[cur].size();
		
		for (int i = 0; i < len; ++i)
		{
			int nextgroup = v[cur][i];
			int ncount = ccount + 1;

			if (!visited[nextgroup])
			{
				visited[nextgroup] = true;

				int elenum = group[nextgroup].size();

				for (int j = 0; j < elenum; ++j)
				{
					if (group[nextgroup][j] == cur)
						continue;

					if (!visitednode[group[nextgroup][j]])
					{
						q.push(make_pair(group[nextgroup][j], ncount));
						visitednode[group[nextgroup][j]] = true;
					}
				}
			}

		}
	}
	
	printf("-1");
	return 0;
}

 

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~