사회망 서비스SNS
문제
- 친구 트리가 주어 질 때 얼리 아답터의 수를 최소로 하여 새로운 아이디어를 전파하라!
- 아이디어를 전파하기 위해서는 얼리 아답터이거나 모든 친구가 얼리 아답터여야만 한다.
- 예를 들어 1번과 2번이 친구이고 2번과 3번이 친구인경우 2번이 얼리 아답터라면 1번과 3번 모두에게 아이디어가 전파가능하다. 하지만 1번이나 3번만 얼리 아답터라면 나머지 모두에게 아이디어가 전파돼지 않는다.
입력
- 첫 번째 줄에는 트리의 정점 개수 N이 주어진다. (2<=N<=1000000)
- 다음 줄부터 N-1개의 친구 관계가 주어진다.
출력
- 얼리 아답터의 최소 수를 하나의 정수로 출력
(Solution)
DFS가 이 문제와 잘 어울릴 것 같아서 규칙을 만들어서 풀었다.
DFS과정에서는 다음의 규칙을 따랐다.
- 리프 노드들은 친구가 한명만 존재하므로 리프 노드와 연결되어 있는 노드들부터 얼리아답터로 만들어 준다.
- 자신이 얼리 아답터라면 그냥 넘어간다.
- 자신이 얼리 아답터가 아닌 경우 친구가 모두 얼리 아답터인지 체크한 후에 자신과 연결된 친구 중 한명만 얼리 아답터가 아니거나 모두 얼리 아답터라면 또한 넘어간다.
- 그렇지 위에 두 조건을 만족하지 않는다면 그 노드는 얼리 아답터가 된다.
- 루트노드인 경우 친구가 모두 얼리 아답터가 아니라면 자신이 얼리 아답터가 된다.
이 문제에서 루트 노드에서만 특별 규칙을 적용하는 이유는 루트 노드의 경우 위로 올라갈 수 없기 때문에 모든 친구가 얼리 아답터여야만 한다.
다른 노드의 경우 올라가면서 다른 노드가 얼리 아답터가 될 수 있다면 더 얼리 아답터의 수로 모든 아이디어를 전파 할 수 있다. 이 문제는 dfs말고도 dp로도 가능하다 하니 다음에 한번 풀어보아야 겠다.
coding chobo