글 읽기 - 1108번 검색 엔진 질문입니다.

kks227 7년 전 0

서로 직/간접적으로 도달할 수 있으면 점수를 더해주지 않는다는 것을 같은 SCC 안에 속해있으면 점수를 더해주지 않는 것으로 생각하고

각 사이트를 정점으로 하여 SCC별로 분리하고, SCC 단위로 위상 정렬한 후 그 순서대로 원래의 사이트들을 방문해가며

u->v 간선의 경우 u와 v가 같은 SCC에 속해 있지 않을 경우에만 u의 점수를 v에 더해주는 식으로 문제를 풀었습니다.

29%까지는 도달하고 틀렸다는 판정을 받았는데, 뭔가 문제나 예외가 존재하나요?

등장할 수 있는 사이트 개수는 마지막 줄을 제외하고 50*50 = 2500개라 생각했습니다.

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
typedef map<string, int> SIM;

int cnt, dfsn[2500], SN, sn[2500];
vector<int> adj[2500];
bool finished[2500];
stack<int> S;
vector<vector<int>> scc;

int dfs(int curr){
	dfsn[curr] = ++cnt;
	S.push(curr);
	int result = dfsn[curr];
	for(int next: adj[curr]){
		if(dfsn[next] == 0) result = min(result, dfs(next));
		else if(!finished[next]) result = min(result, dfsn[next]);
	}
	if(result == dfsn[curr]){
		vector<int> curscc;
		while(1){
			int n = S.top();
			S.pop();
			curscc.push_back(n);
			finished[n] = true;
			sn[n] = SN;
			if(n == curr) break;
		}
		scc.push_back(curscc);
		SN++;
	}
	return result;
}

int main(){
	int N, V = 0;
	cin >> N;
	SIM M;
	SIM::iterator finder;
	// 입력받으며 각 사이트명에 번호를 붙이고 그래프 제작
	for(int i=0; i<N; i++){
		string site;
		int u, v, K;
		cin >> site >> K;
		finder = M.find(site);
		if(finder != M.end()) u = finder->second;
		else M[site] = u = V++;

		for(int j=0; j<K; j++){
			string link;
			cin >> link;
			finder = M.find(link);
			if(finder != M.end()) v = finder->second;
			else M[link] = v = V++;
			adj[v].push_back(u);
		}
	}
	// SCC 뽑기
	for(int i=0; i<V; i++)
		if(dfsn[i] == 0) dfs(i);

	// sIndegree[i]: i가 속한 SCC 컴포넌트의 indegree
	// sOrder[i]: SCC DAG를 위상 정렬한 결과 i번째 SCC
	int sIndegree[2500] = {0}, sOrder[2500];
	vector<int> sAdj[2500];
	for(int i=0; i<V; i++){
		int Si = sn[i];
		for(int j: adj[i]){
			int Sj = sn[j];
			if(Si == Sj) continue;
			sAdj[Si].push_back(Sj);
			sIndegree[Sj]++;
		}
	}
	// SCC 묶음으로 위상 정렬하여 SCC DAG 구축
	queue<int> Q;
	for(int i=0; i<SN; i++)
		if(sIndegree[i] == 0) Q.push(i);
	for(int i=0; i<SN; i++){
		int curr = Q.front();
		Q.pop();
		sOrder[i] = curr;
		for(int next: sAdj[curr])
			if(--sIndegree[next] == 0) Q.push(next);
	}

	int score[2500] = {0};
	fill(score, score+V, 1); // 모든 사이트 점수 1로 초기화
	// 모든 정점을 SCC 위상 정렬 순서대로 돌며, 자신과 다른 SCC에 속해있는 이웃에게만 점수 더해줌
	for(int k=0; k<SN; k++)
		for(int i: scc[sOrder[k]])
			for(int j: adj[i])
				if(sn[i] != sn[j]) score[j] += score[i];

	string dest;
	cin >> dest;
	finder = M.find(dest);
	if(finder != M.end()) cout << score[finder->second] << endl;
	else cout << 1 << endl; // 경악스럽게도 마지막에 물어본 사이트 이름이 한 번도 안 등장한 경우
}

kks227 7년 전 4

아... int 범위를 넘어가네요. 해결되었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1108번 검색 엔진 질문입니다.

kks227 7년 전 0

kks227 7년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말