[백준/BOJ] 백준 1108번 : 검색 엔진

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

1108번: 검색 엔진

타잔 알고리즘을 이용해 SCC를 구하고, SCC끼리의 그래프를 만드는데 SCC 간의 길이 여러 개 있어도 연결은 하나만 만든다. 그리고 SCC 그래프의 위상 정렬을 하며 here_scc와 there_scc에 속한 노드들 중 서로 직접적으로 연결된 길이 있을 때 점수를 부여하는 방식으로 문제를 해결했다.

 

코드

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

int n;
string dest;
int site_number_cnt = 0;
map<string, int> site_number; //(사이트 이름, 사이트를 구별할 번호)
vector<int> adj[2501];
vector<vector<int>> connected(2501, vector<int>(2501, 0)); //[정점1][정점2] = (정점1에서 정점2로 직접 연결 되어 있으면 1)

//타잔 알고리즘(SCC, 강한 연결 요소) 사용
vector<int> visited(2501, 0);
vector<int> maked(2501, 0);
vector<int> node_id(2501, 0);
int node_id_cnt = 0;
stack<int> st;
int scc_id_cnt = 0;
vector<vector<int>> scc(2501);
vector<int> node_scc_id(2501);
vector<int> scc_adj[2501];
vector<vector<int>> scc_connected(2501, vector<int>(2501, 0)); //[scc1][scc2] = (scc1에서 scc2로 직접 연결 되어 있으면 1)
vector<int> indegree(2501, 0);
vector<long long> score(2501, 1);
queue<int> q;

//SCC로 나눈다
int Dfs(int here)
{
	visited[here] = 1;

	node_id_cnt++;
	node_id[here] = node_id_cnt;

	st.push(here);

	int parent = node_id[here];

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

		if (visited[there] == 0)
		{
			parent = min(parent, Dfs(there));
		}

		else if (maked[there] == 0)
		{
			parent = min(parent, node_id[there]);
		}
	}

	if (parent == node_id[here])
	{
		scc_id_cnt++;
		vector<int> this_scc;

		while (1)
		{
			int st_top = st.top();
			st.pop();

			this_scc.push_back(st_top);
			node_scc_id[st_top] = scc_id_cnt;
			maked[st_top] = 1;

			if (st_top == here)
				break;
		}

		scc[scc_id_cnt] = this_scc;
	}

	return parent;
}

//scc그래프의 위상정렬 이용
long long Solve(int dest)
{
	for (int i = 1; i <= scc_id_cnt; i++)
	{
		if (indegree[i] == 0)
		{
			q.push(i);
		}

	}

	while (!q.empty())
	{
		int here_scc = q.front();
		q.pop();

		for (int i = 0; i < scc_adj[here_scc].size(); i++)
		{
			int there_scc = scc_adj[here_scc][i];

			for (int a = 0; a < scc[here_scc].size(); a++)
			{
				for (int b = 0; b < scc[there_scc].size(); b++)
				{
					int u = scc[here_scc][a];
					int v = scc[there_scc][b];

					//직접적으로 연결된 길이 있을때
					if (connected[u][v] == 1)
					{
						score[v] += score[u];
					}
				}
			}

			indegree[there_scc]--;

			if (indegree[there_scc] == 0)
				q.push(there_scc);
		}
	}

	return score[dest];
}

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string to;
		int from_number;
		string from;

		cin >> to >> from_number;

		//처음 발견한 사이트일때
		if (site_number.count(to) == 0)
		{
			site_number_cnt++;
			site_number.insert(make_pair(to, site_number_cnt));
		}

		for (int j = 0; j < from_number; j++)
		{
			cin >> from;

			//처음 발견한 사이트일때
			if (site_number.count(from) == 0)
			{
				site_number_cnt++;
				site_number.insert(make_pair(from, site_number_cnt));
			}

			connected[site_number[from]][site_number[to]] = 1; //from에서 to로 가는 길이 있다고 체크
			adj[site_number[from]].push_back(site_number[to]);
		}
	}

	cin >> dest;

	for (int i = 1; i <= site_number_cnt; i++)
	{
		if (visited[i] == 0)
		{
			Dfs(i);
		}
	}

	for (int i = 1; i <= site_number_cnt; i++)
	{
		int here = i;
		for (int j = 0; j < adj[i].size(); j++)
		{
			int there = adj[i][j];

			//scc간의 연결은 하나만 만든다
			if (node_scc_id[here] != node_scc_id[there] && scc_connected[node_scc_id[here]][node_scc_id[there]] == 0)
			{
				scc_adj[node_scc_id[here]].push_back(node_scc_id[there]);
				indegree[node_scc_id[there]]++;
				scc_connected[node_scc_id[here]][node_scc_id[there]] = 1; //scc간의 연결 체크
			}
		}
	}

	cout << Solve(site_number[dest]) << "\n";

	return 0;
}