[백준/BOJ] 백준 1649번 : 택시

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

1649번: 택시

위상 정렬을 이용하여 이동을 하면서 어떤 교차로로 갈 때 해당 교차로로 들어오는 교차로의 지금까지 만난 중간지점의 개수를 고려하여 만난 중간지점의 개수가 이전에 들어왔던 교차로의 만난 중간지점의 개수보다 클 때와 같은 경우에 따라 고려하며 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

int n, m;
vector<int> adj[1001];
int a, b, k;
vector<int> c_check(1001, 0);
vector<long long> cache(1001, 0);
vector<int> indegree(1001, 0);
vector<int> mid_max(1001, 0); //지금까지 해당 지점으로 가는 경로중 중간지점의 최대 개수 

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);

		indegree[v]++;
	}

	cin >> a >> b >> k;

	for (int i = 0; i < k; i++)
	{
		int c_i;
		cin >> c_i;

		c_check[c_i] = 1;
	}

	queue<pair<int, int>> q; //(위치, 해당 위치까지 방문한 들려야할 중간 지점의 개수)
	int start_mid = 0;

	//시작지점이 들려야할 중간지점일때
	if (c_check[a] == 1)
		start_mid++;

	mid_max[a] = start_mid;
	cache[a] = 1;

	//q.push(make_pair(a, start_mid));
	//indegree가 0인데 시작점이 아닌 지점에서 중간 지점으로 가는 그래프 상황도 고려해야 된다
	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] == 0)
			q.push(make_pair(i, mid_max[i]));
	}


	while (!q.empty())
	{
		int here = q.front().first;
		int here_mid = q.front().second; //현재까지 만난 중간지점의 개수
		q.pop();

		if (here == b)
			break;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];
			int there_mid = here_mid;

			if (c_check[there] == 1)
				there_mid++;

			indegree[there]--;

			if (mid_max[there] < there_mid)
			{
				cache[there] = cache[here];
				mid_max[there] = there_mid;
			}

			else if (mid_max[there] == there_mid)
			{
				cache[there] += cache[here];
			}

			if (indegree[there] == 0)
			{
				q.push(make_pair(there, mid_max[there]));
			}
		}
	}

	//중간경로를 모두 다 방문 했을때
	if (mid_max[b] == k)
		cout << cache[b];
	else
		cout << 0;

	return 0;
}