[Leetcode] 968. Binary Tree Cameras

문제 : https://leetcode.com/problems/binary-tree-cameras/

---

이진트리의 루트 노드가 주어진다.

노드의 각 카메라가 부모, 자신, 직계 자식 노드를 모니터링 할 수 있는 트리 노드에 카메라를 설치한다.

트리의 모든 노드를 모니터링 하는데 필요한 최소 카메라 수를 구하라.

---

DFS로 최하단에 있는 노드들부터 상태를 갱신하면서 탐색한다.

각 노드들에서 나타날 수 있는 경우는 총 3가지이다.

1. Not Monitored : 모니터링 되고 있지 않은 상태이다. (이 경우 부모 노드에서 처리하도록 한다.)

2. Monitored : 모니터링 되고 있는 상태이다.

3. Set Camera : 카메라가 세팅된 상태이다.

 

탐색 중인 노드는 초기 값은 모니터링 되고 있지 않은 상태(1)이며

만일 자식 노드들 중 모니터링 되고 있지 않은(1) 노드가 존재한다면 카메라를 세팅(3)해 감시되어야 한다.

만일 자식 노드들 중 카메라가 세팅(3)된 노드가 존재한다면 현재 노드는 모니터링 되고 있는 상태(2)가 된다.

 

위 방법으로 최하단의 노드부터 노드들 상태를 세팅해나가면서 카메라가 세팅된 노드의 수를 구하면 정답이 된다.

[그림 1]

[그림 1]를 예시로 보자.

1. 최하단의 노드는 모니터링 되고 있지 않은 상태로 탐색이 시작된다.

2. 자식노드들 중 모니터링 되고 있지 않은 상태가 있기 때문에 카메라를 설치한다.

3. 자식노드들 중 카메라가 설치된 노드가 있기 때문에 모니터링 되고 있는 상태이다.

4. 자식 노드들 중 카메라가 설치된 노드도 없고 모니터링 되고 있지 않은 노드도 없기 때문에 모니터링 되지 않는 상태가 된다.

5. 2번과 같다.

6. 3번과 같다.

[그림 2]

[그림 2] 는 루트 노드가 모니터링 되지 않은 상태로 탐색이 종료된다.

이 경우 모든 노드가 모니터링 되고 있지 않고 있으므로 루트 노드가 모니터링 되고 있지 않다면 루트 노드에 카메라를 설치하여 주어야 한다.

 

V = 노드 수, E = 간선 수. 

시간복잡도는 O(V+E)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/968.%20Binary%20Tree%20Cameras.cpp

---

예전에 비슷한 문제 풀어본거 같은데 기억이 안난다..