(BOJ) 17209 새내기와 헌내기

문제: https://www.acmicpc.net/problem/17209

 

문제 풀이:

현재 보는 사람이 새내기라면 그가 지목한 사람들은 헌내기

현재 보는 사람이 헌내기라면 그가 지목한 사람들은 새내기

즉, 항상 반대 이므로 두가지 경우를 다 돌려줄 필요가 없음

 

dfs를 이용하여 한 사람을 새내기(새내기=1)라고 두고 그가 지목한 사람은 헌내기(헌내기++)

그 헌내기가 지목한 사람은 새내기(새내기++)

해줘서 max(새내기,헌내기)를 결과 값에 더해준다.

 

 

소스 코드:

int n,res,people[2];
bool visit[2001];
vector<vector<int>> adj;

void func(int cur,bool old) {
	if (visit[cur]) return;
	visit[cur] = true;
	for (int i : adj[cur]) {
		if (visit[i]) continue;
		people[!old]++;
		func(i,!old);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n;
	adj.resize(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++){
			char a;
			cin >> a;
			if (a == '1') {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (visit[i]) continue;
		people[0] = 0;
		people[1] = 0;
		func(i,true);
		res += max(people[0], people[1]+1);
	}
	cout << res << '\n';
}