didwngus01   3년 전

[질문 1 ]

아직 parent도, child도 없는 node가 입력값에 주어질 수 있나요?

예를 들면, N=5일때

(1, 2) (2, 3)  이 주어진 후에 (4, 5)  << 이런 입력값도 주어질 수 있는 건가요?


[질문 2]

6

1 2

2 3

4 5

4 6

1 4

라고 입력이 주어졌으면, (1,4)가 나오기 전까지 6->4->5인지  4->(5,6) 인지 판단할 수 없습니다.


이 문제는 [질문2]와 같은 어려운 상황도 고려해야 되는 문제인가요?

혹시 그렇다면 더 열심히 공부해오겠습니다...

djm03178   3년 전

네, 가능합니다. 그래서모든 간선을 입력받기 전까지는 누가 부모이고 자식인지 판단할 수 없습니다.

특별히 이 문제가 어렵게 하기 위해 그렇게 한 것은 아니고, 트리를 입력으로 주는 문제에서는 가장 흔한 방식입니다. 모든 간선에 대한 정보를 가진 상태에서 탐색을 시작하여 부모 자식의 관계를 어렵지 않게 알아낼 수 있습니다.

didwngus01   3년 전

답변 감사합니다!!

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