lms8147   2년 전

  1. 인접리스트로 트리 구현하기
  2. 구현된 트리를 정점 1부터 시작하여 dfs 탐색하면서 tree 부모관계, 최대 깊이 설정
  3. LCA를 구하고자 하는 두개의 정점의 깊이 차이를 2진 비트를 이용해 없애기
  4. 같아진 두개의 정점에 대해 2^k 단위로 부모를 찾으며 같아지는 최소한의 부모 찾기

위의 과정으로 구현을 해봤습니다.

채점 결과 틀렸습니다가 나오는데 작성자라 그런지 제 눈엔 오류가 보이질 않네요.

저와 다른 시각으로 보시고 오류가 생길법한 구간을 찾아주시면 감사하겠습니다.

lms8147   2년 전

감사합니다.

올려주신 예제 덕분에 문제점을 찾았습니다.

2^k 단위로 부모를 찾아 나가기 위해 JUMP 할 수 있는 최대 k를 구하는 곳에 오류가 있더군요.


트리 최대 레벨 보다 같거나 큰 2^k 를 만족하는 k 를 구하기 위해 

쉬프트 연산을 써서 카운팅을 하는데 올림 보정을 하지않아

만족하는 2^k 가 없는 경우가 생기네요.

--------------------------------------------------------------

올려주신 다른 LCA 해법도 적용해보겠습니다.

emevoluoyod   1년 전

저도 cubelover님 덕분에 런타임 에러 해결했습니다 감사합니다

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