✅ 한 것들

---

• 백준

⚔️ 백준

---

9370 미확인 목적지

틀린 풀이

#include"9370.h"
using namespace std;
typedef pair<int, int> pii;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<int> vi;
typedef vector<bool> vb;

namespace
{
	vvp edges;
	int n, s, g, h;
	vb visited;
	vi minTotalCost;
	vb available;

	void dfs(int node, int totalCost, bool passedGH)
	{
		// dfs로 뚫으면서, 이미 기록된 경로보다 비용 많이 들면 무시
		// 목적지에 도착했는데 g랑 h가 연속되지 않았다면 갱신 안 함
		if (totalCost < minTotalCost[node])
		{
			minTotalCost[node] = totalCost;
			if (passedGH) available[node] = true;
			else available[node] = false;
		}
		else if (totalCost == minTotalCost[node] && passedGH)
		{
			available[node] = true;
		}
		else return;

		bool node1GH = (node == g || node == h);
		
		for (pii edge : edges[node])
		{
			int cost, next;
			tie(cost, next) = edge;
			if (visited[next]) continue;
			bool node2GH = (next == g || next == h);
			visited[next] = true;
			dfs(next, totalCost + cost, passedGH || (node1GH && node2GH));
			visited[next] = false;
		}
	}

	void CheckAvail()
	{
		visited = vb(n+1);
		available = vb(n + 1);
		visited[s] = true;
		minTotalCost = vi(n + 1, 1e9);
		dfs(s, 0, false);
	}
}

void B9370::Solution()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T, m, t;
	cin >> T;
	while (T--)
	{
		// 교차로 = 노드, 도로 = 엣지
		cin >> n >> m >> t; // 교차로, 도로, 목적지 후보 개수
		cin >> s >> g >> h; // 출발지, 지나간 엣지의 두 노드
		edges = vvp(n+1);
		for (int i = 0; i < m; i++)
		{
			// 노드 번호는 자연수 기준
			int a, b, d;
			cin >> a >> b >> d;
			edges[a].push_back({ d,b }); // d가 걸려서 b로 간다
			edges[b].push_back({ d,a });
		}
		vi possible;
		for (int i = 0; i < t; i++)
		{
			int x;
			cin >> x;
			possible.push_back(x);
		}

		// s에서 목적지 후보로 가는 최단 경로 중에,
		// g와 h가 연속으로 있느냐?를 묻는 것.

		sort(possible.begin(), possible.end());
		CheckAvail();
		for (int p : possible) if (available[p]) cout << p << ' ';
		cout << '\n';
	}
}

• 각 목적지에 대해 돌렸더니 1%에서 시간 초과
• dfs는 한 번만 돌렸더니 16%에서 시간 초과
  • 엣지가 최대 5만개라 시간 복잡도 구하는 방법도 모르겠고 캐싱으로 최적화하면 대충 되지 않을까~ 했는데 역시 안됐다. 엣지 제한 없으면 2000!이니까...
• 유형 확인했더니 다익스트라. 최단 경로라는 말이 나온 시점에서 우선적으로 고려했어야 했다.

#include"9370.h"
using namespace std;
typedef pair<int, int> pii;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<int> vi;
typedef vector<bool> vb;

namespace
{
	vvp edges;
	int n, s, g, h;

	void dijk(int refp, vi& minCost)
	{
		priority_queue<pii, vector<pii>, greater<pii>> pq;
		pq.push({ 0, refp });
		minCost[refp] = 0;

		while (!pq.empty())
		{
			int totalCost, node;
			tie(totalCost, node) = pq.top(); pq.pop();
			if (minCost[node] < totalCost) continue;
			for (pii edge : edges[node])
			{
				int cost, next;
				tie(cost, next) = edge;
				if (totalCost + cost >= minCost[next]) continue;
				minCost[next] = totalCost + cost;
				pq.push({ totalCost + cost, next });
			}
		}
	}

	void CheckAvail(vi& possible)
	{
		// 시작점에서부터 s에 대해 다익스트라를 돌린다
		// g와 h에 대해 다익스트라를 돌린다
		// 각 p에 대해,
		// s g h p 또는 s h g p가 s p 최단거리와 같다면 p 출력

		vi minFromS = vi(n + 1, 1e8);
		vi minFromG = vi(n + 1, 1e8);
		vi minFromH = vi(n + 1, 1e8);

		dijk(s, minFromS);
		dijk(g, minFromG);
		dijk(h, minFromH);

		int costSG = minFromS[g];
		int costGH = minFromG[h];
		int costSH = minFromS[h];
		int costHG = costGH;
		for (int p : possible)
		{
			if (minFromS[p] == costSG + costGH + minFromH[p]
				|| minFromS[p] == costSH + costHG + minFromG[p])
				cout << p << ' ';
		}
	}
}

void B9370::Solution()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T, m, t;
	cin >> T;
	while (T--)
	{
		// 교차로 = 노드, 도로 = 엣지
		cin >> n >> m >> t; // 교차로, 도로, 목적지 후보 개수
		cin >> s >> g >> h; // 출발지, 지나간 엣지의 두 노드
		edges = vvp(n+1);
		for (int i = 0; i < m; i++)
		{
			// 노드 번호는 자연수 기준
			int a, b, d;
			cin >> a >> b >> d;
			edges[a].push_back({ d,b }); // d가 걸려서 b로 간다
			edges[b].push_back({ d,a });
		}
		vi possible;
		for (int i = 0; i < t; i++)
		{
			int x;
			cin >> x;
			possible.push_back(x);
		}

		// s에서 목적지 후보로 가는 최단 경로 중에,
		// g와 h가 연속으로 있느냐?를 묻는 것.

		sort(possible.begin(), possible.end());
		CheckAvail(possible);
		cout << '\n';
	}
}

다익스트라로 변경했더니 정답

• 다익스트라 구현할 때 시작 위치 비용 0으로 초기화, 꺼냈을 때 이미 더 낮아져 있는 건, 등호(=)까지는 허용하여 시작점 통과시키기.