트리에서 주어진 연결 관계를 양방향이 되도록 연결하고

이를 visited라는 bool형 배열을 이용하여 방문처리 하여 중복 방문이 없도록 만들었습니다.


제가 생각한 것은

어떤 노드(A)의 하나의 자식(B)만이라도

그 자식(B)의 자식(C)이 없다면 노드(A)가 얼리어답터이면 된다 입니다.

     A

   /  |  \

  C   B  D 

 /

E

A에 대해서 모든 자식들을 방문하여 위의 연산을 처리한다 하였을 때

C의 경우 자식이 존재하므로, A는 얼리어답터일 필요가 없습니다.

C로 재귀적 호출을 통해 넘어갔을 때 C의 자식인 E는 자식이 존재하지 않으므로

C는 얼리어답터일 필요가 있고 더 이상 자식이 존재하지 않으므로 함수를 종료합니다

다시  A로 돌아와  B에 대해서 확인합니다. B는 자식이 존재하지 않으므로,  

A가 얼리어답터일 필요가 있습니다.

D도 마찬가지


이런 식으로 생각했고, 양방향, visited 처리를 해주어 어떤 노드라도

루트일 수 있도록 설계했습니다..

질문에 올라온 예제들을 다 입력해보고

제가 몇 개 만들어서 집어 넣어봐도 정상적으로 출력이 되는데

뭐가 문제죠..? ㅠㅠ 도와주세요!


kesakiyo   4달 전

5

1 2

2 3

3 4

4 5

를 입력하면 답이 제대로 안나오네요~

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