트리. [1086]

[1. 문제 설명]

https://www.acmicpc.net/problem/1068

---

[2. 풀이 접근]

leaf node 는 자식 노드가 없는 노드이므로,

문제에서 요구한 대로, tree 에서 노드를 제거 한 뒤,

자식 노드가 없는 노드의 개수를 세면 된다.

 

다음은 tree 에서 노드를 제거하는 방법이다.

아래 그림에서 a 노드를 제거해야 할 때, a 와 연결된 그 자식 노드만 제거한다면 (그 연결을 끊는다면),

d, e 노드가 제거되지 않는다.

즉, 제거할 노드를 root 로 하는 서브 트리를 전체 tree 에서 제거해야 한다.

tree 는 재귀적인 성질을 갖고 있으므로,

이 sub tree 역시 재귀적인 방법으로 제거하면 된다.

 

다음은 제거할 노드와 그 부모노드간의 연결성이다.

아래 그림에서 a 노드를 제거하였을 때, 별도 처리를 하지 않으면

root 는 제거된 노드 a 와 연결되어 있다.

즉, leaf node 개수를 제대로 세지 못하는 상태가 되는 것이다.

그래서 a 의 부모 노드에 접근해서 부모 노드와 a 노드 간 연결성을 제거해야 한다.

 

끝으로 구현 상 실수할만 한 부분이다.

트리에서 제거된 노드는 자식 노드가 없으므로, 자식 노드 개수가 0 이다.

그런데 트리에서 제거된 노드의 자식 노드 개수가 0 인 것과,

leaf node 가 되서 자식 노드 개수가 0이 된 것을 구분할 방법이 없다.

이 경우 노드의 제거 유무를 저장 할 추가 배열을 할당하여 해결하도록 한다.

(golang 으로 작성했으면, nil 을 사용해서 간단히 처리할 수 있었는데... 이 부분이 아쉽다.)

---

[3. 코드]