[백준] 3977 축구 전술💫

⚡백준 3977 축구 전술

• https://www.acmicpc.net/problem/3977

• 강결합 컴포넌트(SCC)의 위상 정렬 문제

풀이

⚡SCC의 indegree 계산하기

• 타잔 알고리즘에서 이미 방문한 정점 there이 SCC에 속해 있는지를 확인할 때,
  -> there이 이미 SCC에 속해있는 경우: 교차 간선 (here, there)를 통해 해당 SCC로 접근 가능
  -> there을 포함한 SCC의 indegree를 증가시켜준다

• 타잔 알고리즘에서 스택 속 here과 같은 SCC에 포함되는 정점들을 모두 꺼내며 SCC를 그룹화할 때,
  -> 스택이 비지 않은 경우: here보다 높은 위치의 정점들로부터 해당 SCC가 접근 가능
  -> here을 포함한 SCC의 indegree를 증가시켜준다

틀린 코드

• 16%에서 틀렸습니다
  어디가 문제인건지 더 고민해봐야겠다

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int V, E;
vector<vector<int>> adj;

int vertexCounter;
vector<int> discovered;

int sccCounter;
//sccId[i]: 정점 i가 포함된 강결합 컴포넌트의 sccId
vector<int> sccId;
//indegree[sccId]: sccId를 갖는 강결합 컴포넌트의 진입 차수
vector<int> indegree;
//sccComponent[sccId]: sccId를 갖는 강결합 컴포넌트에 포함된 정점의 집합
vector<vector<int>> sccComponent;

//정점의 번호를 담는 스택
stack<int> st;

int scc(int here) {
	discovered[here] = vertexCounter++;
	int ret = discovered[here];

	//스택에 here을 넣는다
	//here의 자손들은 모두 스택에서 here 위에 쌓이게 된다
	st.push(here);

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

		//(here, there)이 트리 간선인 경우
		if (discovered[there] == -1) {
			ret = min(ret, scc(there));
		}
		//(here, there)이 무시해야하는 교차 간선이 아닌 경우
		else if (sccId[there] == -1) {
			ret = min(ret, discovered[there]);
		}
		//(here, there)이 무시해야하는 교차 간선인 경우
		else {
			indegree[sccId[there]]++;
		}
	}

	//here에서 부모로 올라가는 간선을 끊어도 되는 경우 
	if (ret == discovered[here]) {
		//here을 루트로 하는 서브트리에 남아 있는 정점들을 하나의 컴포넌트로 묶는다
		vector<int> component;
		while (true) {
			int t = st.top();
			st.pop();
			
			sccId[t] = sccCounter;
			component.push_back(t);

			if (t == here) break;
		}

		if (!st.empty()) {
			indegree[sccId[here]]++;
		}

		sort(component.begin(), component.end());
		sccComponent.push_back(component);
		sccCounter++;
	}
	return ret;
}

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

	int t;
	cin >> t;
	while (t--) {
		cin >> V >> E;

		//초기화
		vertexCounter = sccCounter = 0;
		adj = vector<vector<int>>(V, vector<int>(0));
		discovered = vector<int>(V, -1);
		sccId = vector<int>(V, -1);
		indegree = vector<int>(V, 0);

		//그래프 입력 받기
		for (int i = 0; i < E; ++i) {
			int A, B;
			cin >> A >> B;
			adj[A].push_back(B);
		}
		
		//scc all
		for (int i = 0; i < V; ++i) {
			if (discovered[i] == -1)
				scc(i);
		}

		//진입 차수 0인 강결합 컴포넌트 1개 이상인 경우 Confused
		int ans = -1;
		bool confused = false;
		for (int i = 0; i < sccCounter; ++i) {
			if (indegree[i] == 0) {
				if (ans == -1) ans = i;
				else { 
					confused = true;
					break; 
				}
			}
		}
		if (confused) {
			cout << "Confused\n";
			cout << "\n";
			break;
		}
		for (int i = 0; i < sccComponent[ans].size(); ++i)
			cout << sccComponent[ans][i] << "\n";
		cout << "\n";
	}

	return 0;
}

📌 참고자료

• 백준 3977 축구 전술 풀이
  https://everenew.tistory.com/135