ababc1005   11달 전

트리를 모두 받은 다음,

임의의 루트 노드를 정하고 (아래 코드에서는 1번 노드)

dfs로 순회하면서 각 노드들의 루트노드로부터의 거리 dist 를 계산한 뒤,

a노드와 b노드가 호출되면

a와 b의 최소공통조상 c노드를 찾고

(dist_a + dist_b - 2*dist_c)를 리턴하도록 알고리즘을 작성했습니다.

이렇게 제출하니 소요시간이 딱 1000ms 정도로 나오는데,

다른 분들은 대부분 100ms 안쪽으로 AC를 받으셨더라구요...

그래서 코드에 시간낭비되는 부분이 어디가 있나 싶어 글 올립니다.


중간에 뻔한 실수만 하지 않았다면 예상되는 부분은

1. 루트노드 설정이 너무 안일함 -> 미리 height 값을 예상해서 최저 height를 만들어주는 노드로 루트노드 선정

2. 최소공통조상을 찾는 더 효율적인 방법이 있음 (하나씩 거슬러 올라가며 depth를 같게 맞추고, 동시에 하나씩 줄이는 방식입니다.)

둘 중 하나일거 같은데 무엇일지 궁금하네요!

bnb2011   11달 전

로직은 문제가 없는데, 트리를 구성할 때 노드를 동적으로 할당해서 만들어 주는 부분이 많이 느릴 것 같습니다.

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