백준 1108: 검색 엔진

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

 

가벼운 마음으로 도전

이 문제는 가볍게 "위상 정렬"을 사용하면 쉽게 사용할 것이라 생각해서 도전하였다.

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

unordered_map<string, int> um;
int N, cnt = 0, L, indegree[1201], ans[1201];
bool adj[1201][1201], v[1201];
string S, D, Q;
void dfs(int here)
{
	for(int i = 0;i < cnt; i++)
		if (adj[here][i])
		{
			if (v[i])
			{
				adj[here][i] = false;
				continue;
			}
			else
			{
				v[i] = true;
				dfs(i);
			}
		}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> S;
		cin >> L;
		if (um.find(S) == um.end()) um[S] = cnt++;
		int t = um[S];
		while (L--)
		{
			cin >> D;
			if (um.find(D) == um.end()) um[D] = cnt++;
			int f = um[D];
			adj[f][t] = true;
		}
	}
	v[0] = true;
	dfs(0);
	queue<int> q;
	for (int i = 0; i < cnt; i++)
	{
		ans[i] = 1;
		for (int j = 0; j < cnt; j++)
			if (adj[i][j])
				++indegree[j];
	}
	for (int i = 0; i < cnt; i++) if (indegree[i] == 0) q.push(i);
	while (!q.empty())
	{
		int here = q.front();
		q.pop();
		for (int i = 0; i < cnt; i++)
		{
			if (adj[here][i])
			{
				--indegree[i];
				ans[i] += ans[here];
				if (indegree[i] == 0) q.push(i);
			}
		}
	}
	cin >> Q;
	cout << ans[um[Q]] << '\n';
}

문제의 문단

이 문단만 없었다면 맞았을 코드였다.

 

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

 

뒤늦게 이 문단을 발견한 나는 SCC 사용을 고려하였다. 왜냐하면, SCC(Strongly Connected Component)는 긴밀히 연결된 정점 집합이라서, SCC가 같은 정점끼리는 연결하지 않고, 위상정렬을 하면 위의 문단은 문제가 되지 않는다.

자주 사용되는 SCC 알고리즘 중 하나인 타잔 알고리즘을 사용해서, 구현한 결과는 다음과 같았다.

#include <iostream>
#include <unordered_map>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;
stack<int> st;
unordered_map<string, int> um;
int N, cnt = 0, L, indegree[1201], ans[1201], v[1201], vcnt = 0, ssc[1201], sscCnt=0;
bool adj[1201][1201];
string S, D, Q;
int dfs(int here)
{
	int ret = v[here] = vcnt++;
	st.push(here);
	for (int i = 0; i < cnt; i++)
	{
		if (i == here) continue;
		if (v[i] < 0)
			ret = min(ret, dfs(i));
		else if (ssc[i] < 0)
			ret = min(ret, v[i]);
	}
	if (ret == here)
	{
		while (true)
		{
			int t = st.top();
			st.pop();
			ssc[t] = sscCnt;
			if (t == here) break;
		}
		++sscCnt;
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(v, -1, sizeof(v));
	memset(ssc, -1, sizeof(ssc));
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> S;
		cin >> L;
		if (um.find(S) == um.end()) um[S] = cnt++;
		int t = um[S];
		while (L--)
		{
			cin >> D;
			if (um.find(D) == um.end()) um[D] = cnt++;
			int f = um[D];
			adj[f][t] = true;
		}
	}
	v[0] = true;
	for (int i = 0; i < cnt; i++)
		if (v[i] < 0)
			dfs(i);
	while (!st.empty())
	{
		ssc[st.top()] = sscCnt++;
		st.pop();
	}
	for (int i = 0; i < cnt; i++)
		for (int j = 0; j < cnt; j++)
			if (adj[i][j] && ssc[i] == ssc[j])
				adj[i][j] = false;
	queue<int> q;
	for (int i = 0; i < cnt; i++)
	{
		ans[i] = 1;
		for (int j = 0; j < cnt; j++)
			if (adj[i][j])
				++indegree[j];
	}
	for (int i = 0; i < cnt; i++) if (indegree[i] == 0) q.push(i);
	while (!q.empty())
	{
		int here = q.front();
		q.pop();
		for (int i = 0; i < cnt; i++)
		{
			if (adj[here][i])
			{
				--indegree[i];
				ans[i] += ans[here];
				if (indegree[i] == 0) q.push(i);
			}
		}
	}
	cin >> Q;
	cout << ans[um[Q]] << '\n';
}

사소한 실수

그런데, 놀랍게도 이 코드는 틀렸다. 분명 개념은 맞을텐데, 어디서 코드를 잘못 구현했던 걸까?

이 뒤로는 여러가지로 시도를 했다. 이전에 다른 문제에서 인접 행렬을 인접 리스트로 수정해서, 맞은 경험이 있었기에, 바꿔도 보았고

vector<int> adj[MAX]

...

for (int i = 0; i < N; i++)
	{
		cin >> S;
		cin >> L;
		if (um.find(S) == um.end()) um[S] = cnt++;
		int t = um[S];
		while (L--)
		{
			cin >> D;
			if (um.find(D) == um.end()) um[D] = cnt++;
			int f = um[D];
			adj[f].push_back(t);
		}
	}

SCC 비교를 다른 방식으로도 시도해보았다.

for (int i = 0; i < cnt; i++)
{
	ans[i] = 1;
	for (int j = 0; j < cnt; j++)
		if (adj[i][j] && ssc[i] != ssc[j])
			++indegree[j];
}

...

if (adj[here][i] && ssc[here] != ssc[i])
{
	--indegree[i];
	ans[i] += ans[here];
	if (indegree[i] == 0) q.push(i);
}

배열 크기도 좀 더 키웠다.

 

 

결국 어느쪽도 틀린 나는 구글링을 거쳤지만, 다른 분들의 코드들도 내 코드와 다를것이 없었다.

그래도 다른 분 코드를 일일히 비교해 본 결과, 값 배열이 long long 타입인 것을 발견한다.

이 문제는 long long 타입을 넘지 않을 것이라 생각해서 int형으로 두었는데, 혹시...?

란 생각에 수정한 결과

#include <iostream>
#include <unordered_map>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;
const int MAX = 2501;
stack<int> st;
unordered_map<string, int> um;
int N, cnt = 0, L, indegree[MAX], v[MAX], vcnt = 0, ssc[MAX], sscCnt = 0;
vector<int> adj[MAX], adj2[MAX];
long long ans[MAX];
string S, D, Q;

int dfs(int here)
{
	int ret = v[here] = vcnt++;
	st.push(here);
	for (int there : adj[here])
	{
		
		if (v[there] < 0)
			ret = min(ret, dfs(there));
		else if (ssc[there] < 0)
			ret = min(ret, v[there]);
	}
	if (ret == v[here])
	{
		while (true)
		{
			int t = st.top();
			st.pop();
			ssc[t] = sscCnt;
			if (t == here) break;
		}
		++sscCnt;
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(v, -1, sizeof(v));
	memset(ssc, -1, sizeof(ssc));
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> S;
		cin >> L;
		if (um.find(S) == um.end()) um[S] = cnt++;
		int t = um[S];
		while (L--)
		{
			cin >> D;
			if (um.find(D) == um.end()) um[D] = cnt++;
			int f = um[D];
			adj[f].push_back(t);
		}
	}
	for (int i = 0; i < cnt; i++)
		if (v[i] < 0)
			dfs(i);
	queue<int> q;
	fill(ans, ans + MAX, 1);
	for (int here = 0; here < cnt; here++)
		for (int there : adj[here])
			if (ssc[here] != ssc[there])
			{
				indegree[there]++;
				adj2[here].push_back(there);
			}
	for (int i = 0; i < cnt; i++) if (indegree[i] == 0) q.push(i);
	while (!q.empty())
	{
		int here = q.front();
		q.pop();
		for (int& there : adj2[here])
		{
			ans[there] += ans[here];
			if (--indegree[there] == 0) q.push(there);
		}
	}
	cin >> Q;
	cout << ans[um[Q]] << '\n';
}

맞았다... 너무 사소한 실수였다. 심지어 SCC로 바꾼 뒤의 첫 코드도 long long 타입으로 수정하니 맞았다.

이 실수를 해결하기 위해 많은 시간을 소비했는데, 너무 사소해서 헛웃음이 나왔다.