2533번 - 사회망 서비스(SNS)(python3)

문제 링크: https://www.acmicpc.net/problem/2533

2533번: 사회망 서비스(SNS)

오랜만에 문제를 풀고 또 포스팅을 하네요... 너무 바빠요... 살려주세요...

 

SNS 내 사람들 관계가 tree 형태로 주어져있다고 합니다. 그러니까 cycle이 없다는 이야기죠. 얼리 어답터(ea)라는 개념은 다들 아실텐데, SNS 내 모든 사람들은 ea이거나, 또는 ea가 아니거나 둘 중 하나입니다. ea가 아닌 사람은 연결된 모든 neighbor가 ea여야 새로운 아이디어를 받아들인다고 합니다. ea들은 기본적으로 새로운 아이디어를 받아들인 상태구요.

 

SNS 내 모든 사람의 수와 연결 관계가 주어질 때, 모든 사람들이 새로운 아이디어를 받아들이기 위해 필요한 최소 ea의 수를 구하면 됩니다. 다음은 전체 코드입니다.

 

 

 

문제를 보자마자 아! 트리DP구나! 하고 깨달았습니다. 프로그래머스에 올라온 카카오 문제들 중 트리DP를 써야할 것 같은 문제가 많았는데 실제로 트리DP를 활용해서 문제를 푼 건 이 문제가 처음이네요. 확실히 문제를 조금씩이라도 꾸준히 풀다보면 보이는 시선 자체가 넓어지는 것 같습니다. 남은 건 실제로 문제를 푸는 능력이겠죠!

 

기본 아이디어는, ea가 아닌 사람의 모든 neighbor는 무조건 ea여야 한다는 것입니다. 다르게 말하면 ea가 아닌 사람의 이웃으로 ea가 아닌 사람이 있는 경우가 없어야 한다는 것입니다. 그렇다면, child로부터 root 쪽으로 올라가면서 "내가 ea가 아니라면 내 child들은 모두 ea여야 한다", "내가 ea가 아니라면 내 child는 ea든 아니든 상관 없으니 ea가 적은 쪽을 선택하자" 2가지 방침에 따라 재귀를 수행하면 됩니다. 글을 길게 쓰는 대신 주석을 많이 달아놓았으니 코드를 참고해주세요!