1248. [S/W 문제해결 응용] 3일차 - 공통조상

이 번 문제는 이진 트리가 주어지고 두 정점이 주어졌을 때, 이 두 정점에서 가장 가까운 공통 조상을 찾는 문제입니다.

 

처음 이 문제를 접 했을 때, 각 노드에 대한 방문 여부를 확인할 수 있는 visited 배열을 이용하여 문제를 해결할 수 있다고 생각했습니다. 주어진 접점1에서 루트 노드인 1로 올라가면서 방문하는 접점을 표시하고 접점2에서 루트 노드인 1로 다시 올라가면서 처음으로 방문한 노드가 나온다면 해당 노드가 가장 가까운 공통부모일 것이라고 생각하고 문제를 풀게 되었습니다.

 

시도 1.

이번 문제의 입력이 "부모 자식" 순서로 간선에 연결된 접점을 알려주었습니다. 그래서 부모에서 자식으로 뻗은 간선은 parentEdges, 자식에서 부모로 뻗은 간선을 childEdges에 저장했습니다. 각 2차 배열은 (N+1)*(N+1) 크기로 선언했습니다.

 

이 후 입력 받은 접점 1에서 childEdges를 이용하여 루트 노드까지 이동하며 방문한 노드들을 표시했습니다.

그 다음, 점점 2에서 childEdges를 이용하여 루트 노드까지 이동하고, 이미 방문한 노드를 찾을 때까지 이동했습니다.

 

방문한 노드가 나온다면 해당 노드가 두 접점에 가장 가까운 공통부모이므로 해당 부모에서 parentEdges를 이용해 서브트리에 포함된 노드의 개수를 구할 수 있도록 해주었습니다.

 

결과는 실패였습니다. 초반에 오류 코드를 확인하지 않고 답이 틀렸나보다 해서 다른 시도를 했었는데 계속 실패가 나와 의아했었습니다.

세 번째 실패를 하고 오류 코드를 확인해보니, 런타임 에러였고 다시 한 번 문제의 조건을 살펴보니 메모리 부족이 원인이었습니다.

노드의 개수는 10000개까지 나올 수 있고, 제가 10000*10000의 2차 배열을 선언했으므로 메모리 부족이 일어나는 것이 당연했습니다..;;

 

시도 2.

각 간선들을 저장할 수 있는 타입을 ArrayList로 바꾸어 동적으로 간선들을 저장할 수 있도록 했습니다.

이 후는 시도1과 동일한 방법으로 진행을 했고, 공통 분모의 서브트리 노드 개수를 찾을 때에는 ArrayList를 순회해야 했으므로 iterator를 이용했습니다.

Iterator<Integer> iterator;

iterator = parentEdges[node].iterator();
while(iterator.hasNext()){
	stack.push(iterator.next());
	subtreeSize+=1;
}

 

 

여차저차 해결을 하긴 했지만, 오류 코드를 미리 보지 못해 시간을 조금 지체했던 것이 아쉬웠던 문제였습니다.

사실, 첫 번째 시도 당시 (V+1)*(V+1) 크기의 배열을 선언한 이유는 ArrayList로 선언할 경우 iterator를 사용해야지만 안에 원소를 전체 탐색 할 수 있었기 때문입니다. 해당 과정이 귀찮았고 배열로 선언할 경우 더 편하게 접근할 수 있을 것이라고 생각했었습니다. 하지만, 편하게 사용하려고 했던 점이 런타임 에러의 원인이 되었고 이것 때문에 시간이 지체되게 되었습니다. 그래도 iterator를 처음 사용해봄으로써 해당 사용법을 익힐 수 있었고 다음 문제부터는 ArrayList를 바로 사용할 수 있도록 만들어준 것 같습니다.

이번 문제를 통해 귀찮더라도 문제 조건에 따라 선언하는 배열의 타입을 달리해야 함을 알게 되었습니다.