백준 - 15971번 : 두 로봇 (C++)

풀이 방법 : BFS

두 로봇이 출발점에서 각 방까지 가는데에 이동해야하는 최소 거리를 BFS를 통해 계산해서 구해준 다음 통로를 통해 연결되어 있는 방들을 대상으로 각 방에 도달하는 최소 거리를 더한 값들의 최솟값을 갱신시켜가면 된다.

#include <iostream>
#include <vector>
#include <limits.h>
#include <queue>

using namespace std;

struct RouteInfo
{
	int Dest;
	int Dist;
};

int MinDist[100001][2] = {};
bool Check[100001][2] = {};

void BFS(int StartPos, int Idx, const vector<vector<RouteInfo>>& Graph)
{
	queue<pair<int, int>> qDistInfo;
	pair<int, int> Start(StartPos, 0);
	qDistInfo.push(Start);

	while (!qDistInfo.empty())
	{
		pair<int, int> Cur = qDistInfo.front();
		qDistInfo.pop();

		int Size = Graph[Cur.first].size();

		for (int i = 0; i < Size; ++i)
		{
			RouteInfo NextInfo = Graph[Cur.first][i];
			int RouteDest = NextInfo.Dest;
			int RouteDist = NextInfo.Dist;


			if (Check[RouteDest][Idx])
				continue;

			Check[RouteDest][Idx] = true;

			MinDist[RouteDest][Idx] = Cur.second + RouteDist;
			pair<int, int> Next(RouteDest, Cur.second + RouteDist);

			qDistInfo.push(Next);

		}
	}
}

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, Pos1, Pos2;
	cin >> N >> Pos1 >> Pos2;

	vector<vector<RouteInfo>> vecRoute(N + 1);

	for (int i = 1; i < N; ++i)
	{
		MinDist[i][0] = INT_MAX;
		MinDist[i][1] = INT_MAX;

		int Src, Dest, Dist;
		cin >> Src >> Dest >> Dist;
		RouteInfo Info;
		Info.Dest = Dest;
		Info.Dist = Dist;

		vecRoute[Src].push_back(Info);
		Info.Dest = Src;
		vecRoute[Dest].push_back(Info);
	}

	if (Pos1 == Pos2)
	{
		cout << 0;
		return 0;
	}

	BFS(Pos1, 0, vecRoute);
	BFS(Pos2, 1, vecRoute);

	int Min = INT_MAX;
	MinDist[Pos1][0] = 0;
	MinDist[Pos2][1] = 0;

	for (int i = 1; i <= N; ++i)
	{
		int Size = vecRoute[i].size();

		for (int j = 0; j < Size; ++j)
		{
			int Src = i;
			int Dest = vecRoute[i][j].Dest;

			Min = min(Min, MinDist[Src][0] + MinDist[Dest][1]);
		}
	}

	cout << Min;

}