yukariko   2년 전

루트노드 부터 시작하여 자식노드로 재귀를 하는데

각 재귀는 자신이 early adaptor인지 아닌지를 나타내는 인자를 갖습니다.

만약 자신이 early 라면, 자식은 early 이거나 그렇지 않거나로 재귀를 합니다.

early가 아니라면 자식은 무조건 early로 재귀를 합니다.

그렇게 끝노드까지 재귀를한다음 올라오면서 재귀한 결과중 최소를 찾으면서 올라갑니다.

처음엔 재귀 + dp 로 답을 구하려했는데 틀림이 떠서 dp를 제거했는데도 시간초과가아닌 틀림이 뜨네요..

https://www.acmicpc.net/board/view/1211

에 pichulia님이 올려주신 예제로도 전부 정답이 떴는데

어디가 틀린걸까요?

pichulia   2년 전

3

2 1

3 1

이 데이터로 테스트해보세요.

본문 그 어디를 봐도 u가 v의 부모라는 말은 없습니다.

그냥 둘이 간선으로 연결되어있다고 알려줬을 뿐...

그래서 위에 데이터같은 경우 3번노드가 전혀 고려되지 않고 있음을 알 수 있죠

어디를 어떻게 뜯어고쳐야하는지는 감이 안잡히네요...음...그럼 20000

yukariko   2년 전

헉.. 본질적인 부분부터 문제가 있었군요..

처음부터 다시 생각해봐야 할 것 같습니다 ㅠㅠ

yukariko   2년 전

덕분에 해결했습니다!

tree 구조를 잘 살펴보니 어떤 노드를 기준으로 잡아도 루트라고 할 수가 있네요.

그래서 visit 배열을 활용하는 방법으로 루트노드와 자식노트를 구분하였습니다. 

답변 감사합니다!

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