boj, 백준) 3977. 축구전술(C/C++)

1. 문제 링크

www.acmicpc.net/problem/3977

3977번: 축구 전술

2. 문제 개요

경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A,B)로 표현한다. 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그런데 이러한 시작 구역을 찾는 것이 어려웠다. 적절한 시작 구역을 찾는 프로그램을 작성하시오

 

 

 

3. 문제 힌트

어떠한 시작점을 찾아서 그래프를 전부 순회할 수 있으면 된다.

 

아~~~주 간단히 생각해보자..

DFS - ???? 점 1개를 정하고 순회했을 때... 무한반복될 것 같다..

위상 정렬 - cycle이 없다고는 보장 못함.

BFS -  점 1개에 대해 O(N)만큼 탐색.. 이걸 모든 점에 대해서?? 시간 초과

 

SCC- cycle을 지워줌. DAG로 만들기 때문.

DAG는 해당 컴포넌트에 한 해서 모두 연결되어 있다. 그래서 시작점(진입 차수가 0인)을 바로 찾을 수 있다.

 

 

4. 문제 풀이

SCC만 문제없이 잘 찾아준다면 주어진 그래프는 DAG로 나타낼 수 있다.

*DAG(Directed Acycle Graph, 유향 비순환 그래프)

 

두 그래프가 분리되어 있는 게 입력으로 주어진다면, 한 점에서 순환하는 건 절대 무리다.

따라서, 진입 차수가 0인 정점이 딱 1개 있는 경우, 그 점을 통해 DAG를 모두 순환하는 것은 보장된다.

 

SCC를 구하고, 그 SCC를 반영한 그래프에 대해 진입 차수가 0인 SCC를 구하자.

그 SCC의 요소들이 정답이 된다. (오름차순으로!)

 

SCC알고리즘만 알고 있다면, 그 구한 SCC를 가지고 어떻게 새로운 그래프를 만들 것인지 구현력이 필요한 문제이다.

 

5. 코드

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

int t, n, m, cnt;
vector<vector<int>> adj, scc;
stack<int> s;
vector<int> dfsn,scc_index, indegree;
vector<bool> finished;


void init()
{
	adj = vector<vector<int>>(n);
	scc = vector<vector<int>>();
	s = stack<int>();
	finished = vector<bool>(n);
	dfsn = scc_index = indegree =vector<int>(n);

	return;
}

//SCC
int dfs(int cur)
{
	s.push(cur);
	dfsn[cur] = ++cnt;

	int ret = dfsn[cur];

	for (int next : adj[cur]) {
		if (dfsn[next] == 0) {
			ret = min(ret, dfs(next));
		}
		else if (!finished[next]) {
			ret = min(ret, dfsn[next]);
		}
	}
	if (dfsn[cur] == ret) {
		vector<int> cc;
		int index = scc.size();

		while (1)
		{
			int val = s.top(); s.pop();
			cc.push_back(val);
			finished[val] = true;
			scc_index[val] = index;
			if (val == cur)
				break;
		}
		scc.push_back(cc);
	}
	return ret;
}


int main()
{
	scanf("%d", &t);

	while (t--)
	{
		scanf("%d %d", &n, &m);

		init();

		for (int i = 0; i < m; ++i) {
			int from, to;
			scanf("%d %d", &from, &to);

			adj[from].push_back(to);
		}

		for (int i = 0; i < n; ++i)
			if (dfsn[i] == 0)
				dfs(i);

		for (int from = 0; from < n; ++from) 
			for (int to : adj[from]) 
				if(scc_index[to] != scc_index[from])
				++indegree[scc_index[to]];
			
		int ans = 0;
		int ans_index;
		for (int i = 0; i < scc.size(); ++i)
			if (indegree[i] == 0) {
				++ans;
				ans_index = i;
			}

		if (ans == 1) {
			sort(scc[ans_index].begin(), scc[ans_index].end());
			for (int next : scc[ans_index])
				printf("%d\n",next);
		}
		else
		{
			printf("Confused\n");
		}
		
		printf("\n");
		scanf("");
	}

	return 0;
}

6. 결과

 

댓글 환영입니다~^^