글 읽기 - scc와 위상정렬 이용한 문제 질문드립니다.

minhye11 4년 전 0

map을 통해 자료를 받아서 scc를 생성해주었고,

scc간에는 점수가 똑같아서 각 scc를 기준으로 한 connect배열을 만들어주었습니다.

그리고 위상정렬을 이용하여 점수를 계산해준것인데 왜 틀렸는지 도무지 모르겠습니다..

도와주세요 ㅠㅠ

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

int V, E;
vector<int> G[2501];
vector<int> T[2501];
vector<vector<int> > scc;
int cur_time; // finish time 체크를 위한 시간 변수
int ft2vtx[2501]; // ft2vtx[n] = finish time이 n인 정점의 번호
bool visit[2501]; // 방문 체크 배열
int scc_visit[2501];
int scc_check = 1;
map <string, int> M;
int key = 1;

int connect[2501][2501];
int in[2501];
long long score[2501];

void dfs(int here)
{
	visit[here] = true;
	for (int there : G[here])
	{
		if (!visit[there])
			dfs(there);
	}
	ft2vtx[++cur_time] = here;
}

// 역방향 dfs
void rdfs(int here, vector<int>& newscc)
{
	newscc.push_back(here);
	visit[here] = true;
	scc_visit[here] = scc_check;
	for (int there : T[here])
	{
		if (!visit[there])
			rdfs(there, newscc);
	}
}


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin >> E; 
    //입력
	for (int i = 0; i < E; ++i)
	{
		string to;
		cin >> to;
		int to_key;
		if (M.find(to) == M.end()) {
			M.insert(make_pair(to, key));
			to_key = key;
			key++;
		}
		else to_key = M.find(to)->second;
		int j;
		cin >> j;
		while (j--) {
			string from;
			cin >> from;
			int from_key;
			if (M.find(from) == M.end()) {
				M.insert(make_pair(from, key));
				from_key = key;
				key++;
			}
			else from_key = M.find(from)->second;
			G[from_key].push_back(to_key);
			T[to_key].push_back(from_key);
		}
	}
	V = M.size();
	// dfs
	for (int root = 1; root <= V; root++) {
		if (visit[root] == 0)
			dfs(root);
	}

	// finish time이 큰 정점부터 역방향 dfs
	memset(visit, 0, sizeof(visit));
	for (int time = V; time >= 1; time--) {
		int root = ft2vtx[time];
		if (visit[root] == 0) {
			vector<int> newscc;
			rdfs(root, newscc);
			scc.push_back(newscc);
			scc_check++;
		}
	}
	scc_check--;

	//각scc를 기준으로 연결을 정리함.
	for (int i = 1; i <= scc_check; i++) {
		for (int j = 0; j < scc[i - 1].size(); j++) {
			int x = scc[i - 1][j];
			for (int k = 0; k < G[x].size(); k++) {
				int y = scc_visit[G[x][k]];
				if (i == y) continue;
				if (connect[i][y] == 0) {
					in[y]++;
				}
				connect[i][y] = 1;
			}
		}
	}

	for (int i = 1; i <= scc_check; i++) {
		score[i] = 1;
	}

	//위상정렬
	queue <int> q;
	for (int i = 1; i <= scc_check; i++) {
		if (in[i] == 0) q.push(i);
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 1; i <= scc_check; i++) {
			if (connect[x][i] == 0) continue;
			score[i] += score[x];
			in[i]--;
			if (in[i] == 0) q.push(i);
		}
	}

	string ans;
	cin >> ans;
	if (M.find(ans) == M.end()) cout << 1;
	else {
		int ans_key = M.find(ans)->second;
		cout << score[scc_visit[ans_key]];
	}

}

kdr06006 4년 전 2

같은 SCC 그룹이라고 전부 다 같은 점수가 아닙니다.

4
A 2 B C
C 1 D
D 1 A
E 2 C D
C

답 : 1

output : 2

다른 SCC인 정점이 간선을 통해서 들어올 때만 점수를 부여해야합니다.

minhye11 4년 전 0

헐... 그 부분도 의심하긴 했는데....

근데 문제를 다시 읽어봐도 링크가 직접 주어져야 한다는 말이 없어서요...

아닌가요ㅠㅠ 제가 문제를 잘못 이해한건가요?

kdr06006 4년 전 0

점수를 더해주는건 "웹사이트 A에 웹사이트 B로 가는 링크가 있다면, 웹사이트 B의 점수에 웹사이트 A의 점수를 더한다." 일 때 입니다.

여기서 추가조건으로 사이클이 생기면 점수를 더하지 않는다는 조건이지 같은 그룹이라고 무조건 같은 점수이진 않습니다.

C로 들어오는 다른 SCC그룹의 정점은 안들어오니 1점입니다.

minhye11 4년 전 0

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

여기서 B가 A를 링크하는것 = B에서 A로의 링크가 직접적으로 또는 간겁적으로 존재하는 것

으로 판단을 했거든요...

문제의 표현이 애매하다고 볼 순 없는걸까요?

kdr06006 4년 전 0

정점 C를 기준으로 볼 때는 그런 간선이 하나도 없습니다.

그래서 1점입니다.

minhye11 4년 전 0

아 그러니까 주신 예제에서는

B->C로 가는 직접 링크는 없지만, B->A->D->C 인 간접 링크가 있어서, 링크가 있으니까 점수를 줘야겠다고 판단할 여지가 있다고 생각해서요.

그래서 직접 링크라고 명시해야하는것이 아닐까 생각했습니다.

minhye11 4년 전 1

어쨌거나 이 문제는 푸신 분이 별로 안계셔서 답을 못받을거라 생각했는데..

빠르게 피드백도 주시고 너무 감사드립니다ㅠㅠ 흑흑

wogudwkd12 7달 전 0

아 저도 똑같은 이유로 헤매고 있었네요. 지문이 되게 모호한거 같습니다.

A의 점수를 B에 더할 때는, B에서 A로의 링크가 직접적으로 또는 간접적으로 없을 때이다

이 지문만 보면 여러 단계 넘어서도 점수가 전파되야 하는건가? 하는 생각이 들 수 있는거 같네요.

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

문제

문제

출처

ICPC

scc와 위상정렬 이용한 문제 질문드립니다.

minhye11 4년 전 0

kdr06006 4년 전 2

minhye11 4년 전 0

kdr06006 4년 전 0

minhye11 4년 전 0

kdr06006 4년 전 0

minhye11 4년 전 0

minhye11 4년 전 1

wogudwkd12 7달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말