11437번 - LCA
[질문 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]와 같은 어려운 상황도 고려해야 되는 문제인가요?
혹시 그렇다면 더 열심히 공부해오겠습니다...
네, 가능합니다. 그래서모든 간선을 입력받기 전까지는 누가 부모이고 자식인지 판단할 수 없습니다.
특별히 이 문제가 어렵게 하기 위해 그렇게 한 것은 아니고, 트리를 입력으로 주는 문제에서는 가장 흔한 방식입니다. 모든 간선에 대한 정보를 가진 상태에서 탐색을 시작하여 부모 자식의 관계를 어렵지 않게 알아낼 수 있습니다.
답변 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
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]와 같은 어려운 상황도 고려해야 되는 문제인가요?
혹시 그렇다면 더 열심히 공부해오겠습니다...