[백준] 1108 검색 엔진 + Unordered_map 해쉬맵으로 사용

문제

새로운 검색 엔진을 만들었다. 이 검색 엔진은 구글을 뛰어넘는 세계 최고의 검색 엔진이기 때문에, 신뢰도가 높은 결과를 보여줘야 한다. 하지만, 사용자가 검색어를 입력했을 때, 이것에 맞는 결과가 수천, 수만개가 될 수 있으므로, 이 중에 어떤 것이 중요하고, 어떤 사이트를 보여줘야 하는지가 큰 문제이다.

구글은 이러한 것을 사이트를 크롤링해서 자체 알고리즘을 이용해서 사이트의 순위를 매긴다.

우리의 검색 엔진은 다음과 같은 방법을 사용할 것이다.

일단 모든 웹사이트에 1점을 준다. 만약에 웹사이트 A에 웹사이트 B로 가는 링크가 있다면, 웹사이트 B의 점수에 웹사이트 A의 점수를 더한다.

예를 들어, 웹사이트가 총 3개가 있다. A, B, C이다. 일단 모든 웹사이트의 점수는 1이다. 이제, 웹사이트 A와 B에 모두 C로 가는 링크가 있다고 하면, C의 점수는 3이 되고, A와 B의 점수는 그대로 1이다. 만약 어떤 검색어가 입력 되었는데, 이 웹사이트 A B C에 모두 해당하는 것이었다면, C가 가장 위에 표시된다.

이런 웹사이트에 점수를 매기는 일이 어려운 이유는 바로, 링크를 교환하는 사이트 들이 있기 때문이다. 이 말은 A가 B를 링크하고, B가 A를 링크하는 것이다. 따라서, 이런 현상으로 점수가 무한대로 늘어나는 것을 방지하기 위해서, A의 점수를 B에 더할 때는, B에서 A로의 링크가 직접적으로 또는 간접적으로 없을 때이다.

링크가 어떻게 되어있는 지가 주어지고, 웹사이트의 이름이 주어질 때, 그 웹사이트의 점수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 링크 정보의 개수 N이 주어진다. 이 N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 링크의 정보가 주어진다. 링크의 정보에 처음 등장하는 문자열은 웹사이트의 이름이고, 그 다음에 등장하는 수는 그 웹사이트를 가리키고 있는 웹사이트 이름의 수이다. 예를 들어, "C 2 A B"는 A에서 C로 가는 링크, B에서 C로 가는 링크가 있다는 의미이다. 마지막 줄에는 점수를 조사해야 할 웹사이트의 이름이 주어진다.

모든 웹사이트의 이름은 길이가 50보다 작거나 같은 알파벳 대문자로 이루어진 문자열이다. 한 웹사이트를 가리키고 있는 웹사이트 이름의 수는 24보다 작거나 같은 음이 아닌 정수이다. 한 웹사이트를 가르키고 있는 웹사이트에 대한 정보는 여러 번 등장하지 않는다. 점수를 조사해야 할 웹사이트의 이름은 반드시 링크의 정보에 등장한다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };


using namespace std;
string X, K, E;
ll x, N, cnt, num;
//타잔
vector<string> st; //스텍
unordered_map<string, ll> v; //방문
unordered_map<string, ll>s; //scc?



set<string> w; //모든 웹
unordered_map<string, vector<string>>adj; //인접리스트
unordered_map<string, ll>n; //위상정렬 들어오는 scc 수
unordered_map<string, ll> dp; //DP배열

vector<string>scc[2502];

ll dfs(string k) {
	st.push_back(k);
	ll parent = v[k] = ++cnt;
	for (auto r : adj[k]) {
		if (!v[r]) {
			parent = min(parent, dfs(r));
		}
		else if (!s[r]) {
			parent = min(parent, v[r]);
		}
	}
	if (parent == v[k]) {
		vector<string>temp;
		num++;
		while (1) {
			auto back = st.back();
			temp.push_back(back);
			st.pop_back();
			s[back] = num;
			if (back == k)break;
		}
		scc[num] = temp;
	}
	return parent;
}
void tarjan() {
	for (auto r : w) {
		if (!v[r])dfs(r);
	}
}
int main() {
	FAST;

	cin >> N;
	rep(i, N) {
		cin >> X >> x;
		w.insert(X);
		while (x--) {
			cin >> K;
			w.insert(K);
			adj[K].push_back(X);
		}
	}
	cin >> E;
	tarjan();
	queue<string>q;

	for (auto r : w) {
		dp[r] = 1;
		for (auto c : adj[r]) {
			if (s[r] != s[c]) {
				n[c]++;
			}
		}
	}
	for(auto i:w){
		if (!n[i])q.push(i);
	}

	while (!q.empty()) {
		auto top = q.front();
		q.pop();
		for (auto r : adj[top]) {
			if (s[top] != s[r]) {
				dp[r] += dp[top];
				if (!(--n[r]))
					q.push(r);
			}
		}
	}
	cout << dp[E];
}

 A의 점수를 B에 더할 때는, B에서 A로의 링크가 직접적으로 또는 간접적으로 없을 때이다. 간접적으로도 링크가 되면 안된다는 뜻은 한 싸이클 내에 A,B가 존재하면 안된다는 뜻입니다.

따라서 그래프를 SCC로 묶어야 합니다

타잔알고리즘으로 SCC로 묶고,

 

A의 점수를 B에 더할때는 A와 B가 서로 다른 scc내에 존재해야합니다.

그리고 다른 SCC에서 들어오지 않는 정점부터 확인을 해야하므로,

위상정렬을 사용해야 합니다.

 

int형을 넘어설 수 있으므로 long long 으로 써야합니다.

 

새로운 자료구조를 사용했습니다. 해쉬 맵을 사용하기위해

 

std::unordered_map을 사용했습니다.

empty( )

• 맵이 비어있는지 확인하는 함수
• if unordered_map is empty, then return 1 else 0

size( )

• 맵의 크기를 확인하는 함수
• return size_type ( unsigned int )

operator [ ]

• 맵에서 key를 통해 value를 지정하는 operator
• map_name[key] = value

find( key )

• 맵에서 key에 해당하는 원소를 찾는 함수
• if key is contained, then iterator else map_name.end()

count( key )

• 맵에서 key에 해당하는 원소의 갯수를 반환하는 함수
• if key is contained, return 1 else 0

insert( {key, value} )

• 맵에 pair<key,value> 를 추가하는 함수
• if key is contained, then not insert

erase( key )

• 맵에서 key에 해당하는 원소를 제거하는 함수
• erase 하는 방법 : 특정 position의 pair 삭제, key를 통해 삭제, 범위 삭제

clear( )

• 맵을 초기화하는 함수