일단 아주 작은 트리부터 생각해보시고요,
큰 트리라고 하더라도 가장 위의 노드는 처리가 되어야할텐데
위의 노드를 떼면 여러개의 조금 더 작은 트리로 분할이 되죠.
그럼 작은 트리에 대해 생각해둔 답이 있으시니까 어떤것부터 해야할지 아실수 있을거에요..
간단하게, 예제 데이타를 여러방법으로 잘라서 손으로 풀어보시면 감이오실거같습니다 ^^
음.. 저도 그 문제 다시 풀어보고 있는데요
우선 수신자가 많은곳이 제일 오래 걸리는건 아닌것 같아요.
다섯개 노드가 연속적으로 연결된 상태랑
다섯개 노드를 바이너리 트리 형태로 연결 했을때랑
도달하는 시간이 다른걸로 봐서는...
위의 분 말씀처럼 저도 작은 트리 형태로 재귀적으로 풀면 될 것 같아요..
근데 코딩 실력이 후달려서 아직 제대로 구현은 못해봤네요ㅎㅎ;;
alsdk123
문제를 보니 최적의 브로드캐스팅 알고리즘을 짜라는 것같은데
가장 오래걸리는 곳부터 먼저 신호를 보내면 될거 같은데요..
어디가 가장 오래 걸리는지 어떻게 알 수가 있는거죠?
단순히 수신자가 많은 곳이 제일 오래 걸리는 것 아닌 거 같아서요..
우선순위를 어떻게 정해야 될지 모르겠네요..
이 문제같은 경우는 어떤식으로 풀어가야 할 지 궁금하네요..
무슨 간단한 방법이 있을까요..?
13년 전