반응형
SMALL
3일차 - 공통조상 자바
-
1248. [S/W 문제해결 응용] 3일차 - 공통조상알고리즘 2023. 7. 8. 14:38
이 번 문제는 이진 트리가 주어지고 두 정점이 주어졌을 때, 이 두 정점에서 가장 가까운 공통 조상을 찾는 문제입니다. 처음 이 문제를 접 했을 때, 각 노드에 대한 방문 여부를 확인할 수 있는 visited 배열을 이용하여 문제를 해결할 수 있다고 생각했습니다. 주어진 접점1에서 루트 노드인 1로 올라가면서 방문하는 접점을 표시하고 접점2에서 루트 노드인 1로 다시 올라가면서 처음으로 방문한 노드가 나온다면 해당 노드가 가장 가까운 공통부모일 것이라고 생각하고 문제를 풀게 되었습니다. 시도 1. 이번 문제의 입력이 "부모 자식" 순서로 간선에 연결된 접점을 알려주었습니다. 그래서 부모에서 자식으로 뻗은 간선은 parentEdges, 자식에서 부모로 뻗은 간선을 childEdges에 저장했습니다. 각 2..