chiller123   9년 전

몇번을 다시 생각해보았지만... 반례가 무엇이 있는지 모르겠네요.

루트에서부터 DFS 방식으로 탐색해 나갑니다.

자식 노드들 중 먼저 방문하는 순서는 하위 노드들의 개수가 많은 것부터 탐색해 나갑니다.

childCount가 하위 직원의 인원을 나타낸 것이고,

childList는 본인 기준으로 바로 아래 lv의 직원들을 담아놓은 것입니다.

kesakiyo   9년 전

안녕하세요.

뉴스전하기 코드를 보면 현재 자식의 수가 가장 많은 노드들 부터 dfs를 시작하는데

가슴에 손을 올리고 다시한번 생각해 보면, 칠러님이 선택하신 일종의 그리디 전략으로는

최적의 해를 구할 수 없다는 것을 알 수 있을겁니다.

과연 많은 자식을 가지고 있다고 해서 가장 먼저 뉴스를 전하는게 올바른 선택일까요?

노드 1, 2가 있다고 가정해 봅시다.

노드 1의 자식노드의 수는 노드 2보다 많습니다.

하지만 노드 1의 자식들은 균형이 잘 맞춰져 있어서 깊이가 그렇게 깊지 않습니다.

그말은 즉 동시에 뉴스를 전해줄 수 있는 노드들이 많다는 말이 되겠죠.

반면에 노드 2는 노드 1보다 자식의 수는 적지만 불행히도 균형이 맞춰져 있지 않아 한쪽으로 치우쳐진

예를들자면 링크드 리스트와 같은 형식을 이루고 있습니다.

동시에 뉴스를 전해줄 사람이 적다는 얘기가 되겠죠.

그렇다면 노드 1과 노드 2중 누구한테 먼저 뉴스를 전해줘야 할까요?

단순히 자식이 많은 노드 1에게 뉴스를 전해줘야 하는것이 최선의 선택일까요?

23

-1 0 1 1 1 2 2 2 3 3 3 4 4 4 0 14 15 16 17 18 19 20 21

이 예제를 돌려보고 잘 생각해 봐요. 손으로 한번 그려보는걸 추천합니다.

chiller123   9년 전

너무 어렵게 생각했었나보네요.

덕분에 해결했습니다. 감사합니다.

infoefficiency   9년 전

ㅎㅎ 친구끼리 뭐하심들 

댓글을 작성하려면 로그인해야 합니다.