[Leet Code] Binary Tree Cameras

기면지·2021년 5월 17일

LeetCode

목록 보기

8/20

안녕하세요!
오늘은 5월 3주차 두번째 알고리즘인 Binary Tree Cameras 풀이를 적어보겠습니다.

문제

요약
주어진 트리의 노드를 카메라를 설치해서 모두 모니터링해야 합니다.
카메라가 설치되면 부모 노드와 바로 아래 자식 노드들을 모니터링할 수 있습니다.
이 때, 필요한 카메라의 최소 개수를 return하는 문제입니다.

처음 시도한 방법

문제를 보면, TreeNode 라는 이진트리 구조체가 고정되어 있습니다.

이 때 효율적으로 카메라 개수를 세려면, leaf 노드부터 검색해야한다고 생각했습니다.
처음에는 정수값으로 확인했는데, 로직이 가독성이 좋지 않고 이해하기 힘들었습니다.

두번째로 시도한 방법

그래서 enum 을 활용해서 자식 노드의 type 을 체크해 현재 노드가 모니터링하고이는 노드인지, 모니터링이 필요한 노드인지 확인했습니다.
조건을 걸어서 필요한 카메라의 개수를 return 했더니 Accept을 받았습니다.

코드 설명

int answer = 0;

Solution 클래스의 전역 변수로 answer 을 초기화해줍니다.

enum Monitoring {
    NONE, MONITORING, REQUIRED
}

enum 은 위와 같이 설정해주었습니다.
dfs 방식을 사용할 것이기 때문에, 자식 노드가 없는 경우도 체크해야합니다.
그래서 노드가 없는 경우 NONE , 모니터링 되고있는 경우 MONITORING , 모니터링이 필요한 경우 REQUIRED 로 설정했습니다.

private Monitoring dfs(TreeNode node) {
    if (node == null) return Monitoring.NONE;
    Monitoring leftType = dfs(node.left);
    Monitoring rightType = dfs(node.right);
    
    // ...
}

leaf 노드까지 들어갔을 때 노드가 존재하지 않는다면 NONE 을 return합니다.
만약 노드가 존재한다면 왼쪽 자식 노드의 타입은 leftType , 오른쪽 자식 노드의 타입은 rightType 으로 설정해 dfs 재귀호출해줍니다.

private Monitoring dfs(TreeNode node) {
	// ...

    if (leftType == Monitoring.NONE && rightType == Monitoring.NONE) return Monitoring.REQUIRED;
    else if ((leftType == Monitoring.MONITORING && rightType != Monitoring.REQUIRED) || (rightType == Monitoring.MONITORING && leftType != Monitoring.REQUIRED))
        return Monitoring.NONE;
    answer++;
    return Monitoring.MONITORING;
}

조건
1. 자식 노드들이 없다면 leaf 노드이므로 REQUIRED 타입을 리턴합니다.
2. 자식 노드 중 한쪽 노드는 모니터링 중이고 다른 한쪽 노드는 모니터링 중이거나 노드가 존재하지 않는다면 아래쪽 노드들이 모두 모니터링 중이라는 뜻이기 때문에 NONE 타입을 리턴합니다.
3. 위의 경우가 아닌 경우에는 카메라를 추가해주고, 모니터링 중이라는 MONITORING 타입을 리턴합니다.

public int minCameraCover(TreeNode root) {
    return (dfs(root) == Monitoring.REQUIRED) ? answer + 1: answer;
}

자, 이제 minCameraCover 함수에서 dfs 함수를 호출할건데, return문에 조건이 할당되어있습니다.
dfs(root) == Monitoring.REQUIRED 라는 뜻은 root 노드부터 leaf 노드까지 모두 체크했는데 root 노드가 모니터링이 필요하다는 뜻입니다.
따라서, 여태까지 체크한 answer 에 1을 더해줍니다.

전체 코드

class Solution {
    int answer = 0;

    public int minCameraCover(TreeNode root) {
        return (dfs(root) == Monitoring.REQUIRED) ? answer + 1: answer;
    }

    private Monitoring dfs(TreeNode node) {
        if (node == null) return Monitoring.NONE;
        Monitoring leftType = dfs(node.left);
        Monitoring rightType = dfs(node.right);

        if (leftType == Monitoring.NONE && rightType == Monitoring.NONE) return Monitoring.REQUIRED;
        else if ((leftType == Monitoring.MONITORING && rightType != Monitoring.REQUIRED) || (rightType == Monitoring.MONITORING && leftType != Monitoring.REQUIRED))
            return Monitoring.NONE;
        answer++;
        return Monitoring.MONITORING;
    }
}

enum Monitoring {
    NONE, MONITORING, REQUIRED
}