[PS] 백준 #3977. 축구 전술

문제 정보

• 난이도: 플래티넘 IV
• 문제 주소: https://www.acmicpc.net/problem/3977
• 이 문제를 푼 이유: 알고리즘 스터디 - SCC

 

문제

World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다. 모든 도현이의 팀 선수들이 이 움직임만을 따라서 이동한다면 승리하리라고 도현이는 확신한다.

도현이는 선수들에게 자신의 전술을 말해주며, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그러나 도현이는 한 가지 간과한 것이 있었는데 그건 선수들이 자신만큼 똑똑하지 않다는 것이다. 선수들은 그러한 시작 구역을 찾는 것이 어려웠다. 이제 당신이 적절한 시작 구역을 찾아줘야 한다.

 

나의 풀이

5번을 틀렸는데 컴파일 에러를 제외하면 전부 33%에서 틀렸습니다가 떴다. 처음에 생각한 아이디어는 "코사라주 알고리즘 + inDegree가 0인 노드의 개수가 2개 이상이면 안됨" 이라고 생각하여 코드를 짰는데 계속 틀렸다. 결국 질의 응답을 보고 inDegree가 0인 SCC의 개수가 2개 이상이면 안된다는 힌트를 알게 되었다. 그래서 노드 단위로 보던 것 대신 SCC단위로 바꾸기 위해 각 노드에 scc 번호와 inDegree를 기록하게 한 후, inDegree가 0인 SCC의 개수를 구해서 1개가 아닐 경우 답을 "Confused"로 출력하였다.

https://www.acmicpc.net/board/view/62614 이 질문글을 보고 inDegree 내용을 추가해줬더니 한번에 "맞았습니다!!"가 떴다. 위 글은 나랑 똑같이 33%에서 틀렸습니다가 뜬다고 하던데 그 이유를 잘 모르겠다..

#include <bits/stdc++.h>

// 33% 틀렸습니다 ??

#define MAX 100000
#define all(x) x.begin(), x.end()

using namespace std;

// 순방향, 역방향
vector<vector<int>> adj, radj;
vector<bool> visited;
stack<int> st;
vector<vector<int>> scc;
vector<int> sccNumNode, inDegree;

// DFS Post Ordering
void go(int n) {
	visited[n] = true;
	for (int a : adj[n]) {
		if (visited[a]) continue;
		go(a);
	}
	st.push(n);
}

void find(int n, int idx) {
	visited[n] = true;
	scc[idx].push_back(n);
	for (int a : radj[n]) {
		if (visited[a]) continue;
		find(a, idx);
	}
	sccNumNode[n] = idx;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;  cin >> t;
	while (t--) {
		scc.clear();

		int n, m;
		cin >> n >> m;

		visited.clear();
		adj.clear();
		radj.clear();
		sccNumNode.clear();
		inDegree.clear();
		visited.resize(n + 1, false);
		adj.resize(n + 1);
		radj.resize(n + 1);
		sccNumNode.resize(n + 1);
		inDegree.resize(n + 1, 0);

		// construct G, G'
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			radj[b].push_back(a);
		}

		for (int i = 0; i < n; i++) {
			if (visited[i]) continue;
			go(i);
		}


		// reset visited
		visited.clear();
		visited.resize(n + 1, false);

		// dfs to find SCCs in G
		int idx = -1;
		while (!st.empty()) {
			int cur = st.top();
			st.pop();
			if (visited[cur]) continue;
			scc.push_back(vector<int>());
			find(cur, ++idx);
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < adj[i].size(); j++) {
				int next = adj[i][j];
				if (sccNumNode[i] != sccNumNode[next])
					inDegree[sccNumNode[next]]++;
			}
		}
		
		int cnt = 0;
		vector<int> answer;
		for (int i = 0; i < scc.size(); i++) {
        	if (inDegree[i] == 0) {
                cnt++;
                for (int j = 0; j < scc[i].size(); ++j)
                    answer.push_back(scc[i][j]);
			}
		}

		if (cnt != 1) {
			cout << "Confused\n";
		}
		else {
			sort(all(answer));
			for (int& nums : answer) {
				cout << nums << "\n";
			}
		}
		cout << "\n";
	}
}

/*
100
4 4
0 1
1 2
2 0
2 3

4 4
0 3
1 0
2 0
2 3

6 6
0 1
1 2
2 0
2 4
1 3
0 5

6 6
4 5
5 0
0 2
2 1
1 0
1 3

6 9
0 1
0 2
0 3
1 2
2 3
3 1
3 4
4 5
4 0

8 9
3 4
4 1
1 2
2 0
0 4
3 5
5 6
6 7
7 3
*/