백준 2533 사회망 서비스

문제링크

https://www.acmicpc.net/problem/2533

---

문제

---

풀이

• 어떤 노드를 얼리어 답터로 지정해야 할까?
  => 가장 끝 노드인 리프노드부터 생각

1. 리프 노드에 아이디어가 전파되기 위해서 리프 노드의 부모 노드는 반드시 얼리어 답터가 되어야 함
   => 리프노드가 얼리어 답터가 될수도 있지만 그것보다 리프노드의 부모노드가 얼리어 답터가 되는경우가 무조건 이득

2. 자식 노드가 전부 얼리어답터라면 자기 자신은 얼리어답터가 아니어도 됨

3. 반대로 자식 중 하나라도 얼리 어답터가 아닌 자식이 있으면 자기 자신은 얼리어답터가 되어야 함

---

시행착오

알고리즘은 정말 간단했으나 구현하는데 생각보다 시간을 들였어요.

p.s.) 사소한 실수도..
( check = dfs(next) || check ) O
( check = check || dfs(next) ) X => (dfs 진입 못하는 경우 발생 ! )

---

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> link[1000001];
int n, ans;
int dfs(int now,int before) {
	int check = 0;
	bool leaf = true;
	for (int i = 0; i < link[now].size(); i++) {
		if (link[now][i]!=before) {
			leaf = false;
			check = (dfs(link[now][i],now) || check);
		}
	}
	if (leaf) return 1;
	if (check == 1) ans++;
	return !check;
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int a, b;
		cin >> a >> b;
		link[a].push_back(b);
		link[b].push_back(a);
	}

	dfs(1, -1);
	cout << ans;
}

---

후기

복잡한 알고리즘이 사용된건 아니라 구현만 잘하면 풀만한 문제였어요.