쿼리당 부모가 누구인지 입력 받습니다. (par[b]=b의 부모는 a이다) 그 다음 반복문으로 x부터 탐색하는데, 일단 자기 자신도 조상이 될 수 있으므로 방문 처리 해주고(bool color[x]=true) 그 다음 쭉 나가다가 루트를 만나면(자신의 부모가 없으면) 반복문 탈출 한 다음, y기준으로 반복문을 또 돌리는데, 이미 간 좌표가 방문 처리가 되어 있다면, 그 시점에서 방문한 노드가 lca이므로 이를 출력하는 로직으로 했는데...50프로에서 계속 틀립니다...ㅠㅠ
playscer 2년 전
로직)
쿼리당 부모가 누구인지 입력 받습니다. (par[b]=b의 부모는 a이다) 그 다음 반복문으로 x부터 탐색하는데, 일단 자기 자신도 조상이 될 수 있으므로 방문 처리 해주고(bool color[x]=true) 그 다음 쭉 나가다가 루트를 만나면(자신의 부모가 없으면) 반복문 탈출 한 다음, y기준으로 반복문을 또 돌리는데, 이미 간 좌표가 방문 처리가 되어 있다면, 그 시점에서 방문한 노드가 lca이므로 이를 출력하는 로직으로 했는데...50프로에서 계속 틀립니다...ㅠㅠ
(26번째 줄이 좀 걸리긴 하는데...어디서 잘못 됐는지 잘 모르겠습니다!)