Count Subtrees With Max Distance Between Cities

Count Subtrees With Max Distance Between Cities

Count Subtrees With Max Distance Between Cities - LeetCode

- 문제 내용 : Tree로 만들어진 Nodes가 있다. Node의 갯수와 Node간의 Brides Array가 주어 졌을때, (순환 하지 않음) 연결 가능한 모든 Node의 Subsets에서 가장 거리가 긴 Distances를 길이로 해서 Array로  Result를 만들어라.

• 예 ) 1거리 2개 2거리 3개가 있다면 [2,3]

- 접근 방법 : Permutation and Masking

가장 우선적으로 착안해야 할 것은 Node의 Subsets을 어떻게 만들어야 하는 것인가 이다.

cities

가령 상기와 같은 tree가 주어 졌다고 하면

• 1,4
• 1,3
• 3,2
• 1,3,2
• 4,1,3
• 4,1,3,2

의 경우의 수가 만들어 질 수 있다.

여러가지 Permutation 방법이 있을 수 있겠지만, Tree 방식을 이용한 Permutation을 사용할 수는 없었다.

• 1 + 4 = 1,4
• 1 + (3 + ( 2)) = 1,3 / 3,2 / 1,3,2

1을 Root로 두고 하위로 내려 가는 방식으로 Permutation을 하게 되면 이런 모습이 나오는데,

1,4,3과 같이 혼합된 형태를 어떻게 처리 해야할지 착안이 되지 않았다.

그래서 bit를 이용한 Permutation을 사용 하였다.

bit permutation

상기 그림과 같이 4개의 Node가 있다고 하면 각 Node는 1또는 0으로 표시가 가능하고 여기서 1은 Subsets의 대상 Node라고 생각 하면 된다.

이경우 나올 수 있는 경우의 수는 2^4이다.

모든 노드를 선택하지 않는 0부터 모든 노드를 선택하는 15까지 사용하면 된다. 

즉 Range 범위는 다음과 같다.

1 ~ (1 << 4) -1

이때 주의 해야 할 것은 반듯이 2개 이상의 Cities가 선택 되어야 한다는 것이다. 

이는 다음과 같은 bit Operation을 통해 처리가 가능하다.

IntValue - 1 & IntValue === 0 then continue;

예를 들자면 

• '10000' 이라는 값이 들어왔을 경우 1을 빼게 되면
• '01111'이 되고 기존 IntValue와 And를 하게 되면
• 0 이 된다.
• 만약, '10010'이라고 생각해 보자 1을 빼게 되면
• '10001'이 되고 기존 IntValue와 And를 하게되면
• '10000'이 된다. 

상기 코드는 bit operation에서 1의 위치가 어디있든 가장 우측에 존재 하는 1을 삭제하는 데 유용하게 사용 가능하다.

1이 하나일경우 삭제하면 0이 됨으로 불필요한 연산을 사전에 방지 할 수있다.

이제 모든 경우의 수를 처리하기만 하면된다.

이때 다음을 고민해야 한다.

• 어느 포인트에서 시작할것인가?
• 한번 지나간 포인트는 어떻게 지울 것인가?
• Reachable 하지 못한 포인트가 있을 경우는 어떻게 처리 할 것인가?

어느 포인트에서 시작할 것인가?

만약 다음과 같은 3개의 포인트가 선택 되었다고 보자.

1에서 시작 포인트를 잡게 되면 1,3/1,4로 최대 1의 거리가 나온다. 그런데 4를 시작으로 잡게 되면 4와 3으로 인해 2의 거리가 된다. 

그래서 결국은 3개의 포인트를 모두 시작 포인트로 두고 실행해 보아야 한다.

물론 Memorization을 통해서 4,3의 경우 3,4와 동일하게 처리해서 속도를 빠르게 하는 방법이 있겠지만 문제를 푸는데는 반듯이 필요한 요소는 아님으로 처리 하지 않는다.

 

한번 지나간 포인트는 어떻게 지울 것인가?

상기 그림을 순서대로 보게 되면 1번을 Start node로 보았을 때 1번이후 4번 4번 이후 3번을 실행하게 되는데, 만약에 4번으로 넘어 갔을 경우 1번 Node가 Visited된걸 모르게 되면, 무한 Loop에 빠지게 됨으로 이를 처리해 줘야 한다.

상기 그림을 기준으로 예를 들자면 다음과 같은 2진수가 선택 되었다고 생각해 보겠다.

• '1101' => 가장 우측부터 1번 노드로 보고 1,3,4번을 선택하였다.

이경우 startNode가 1임으로 

 '1101' ^ 1 << (node-1) => 1100

상기와 같은 bit Operation을 처리하면 1번 node는 bit mask에서 사라지게 된다.

이렇게 사라진 1100 bit mask를 다음 연산시 사용하게 되면 1번 노드를 다시 search하는 경우가 생기지 않는다.

 

Reachable 하지 못한 포인트가 있을 경우는 어떻게 처리 할 것인가?

만약 node를 1번, 2번, 4번 bit mask로 보았을 때 '1011'이 선택 되었다고 하면, 결과는 무었일까?

기본적으로 연속된 Tree subset으로 만족 되지 않음으로 0으로 처리 되어야 한다.

이는 1011의 subtree bitmask를 순차적으로 지워나감으로써 최종적으로 bitmask값이 0이 아니라면 아직 순회 하지 못한 Node가 있는 것임으로 subset tree 처리를 하지 않으면 된다.

 

상기와 같은 내용을 종합해서 코드를 만들면 아래와 같다.

var countSubgraphsForEachDiameter = function (n, edges) {
    let nodes = new Array(n+1).fill(0).map(_=> new Array());
    let resultArr = new Array(n - 1).fill(0);
    for (let [source, dest] of edges) {
        nodes[source].push(dest);
        nodes[dest].push(source);
    }

    let permutation = 1 << n;

    for (let i = 1; i < permutation; i++) {
        if(((i-1) & i) === 0) continue; //1이 하나만 있는 것은 의미가 없다 2개 이상이어야 한다

        let subtree = i;
        let startNode = 0;
        let result = 0;

        for(let j = 0; j < n; j++){ //우측에서 좌측으로 node 번호가 늘어난다.
            if( subtree & (1 << j)) {
                startNode = j + 1; //node가 1번 부터 임으로 node 번호 + 1을 해줘야 한다.
                let tmpSubtree = subtree;
                let tmpVal = Math.max(result, dfs(startNode, 0));

                function dfs(startNode, max){
                    let count = max;
                    tmpSubtree = tmpSubtree ^ 1 << (startNode - 1); //clear point
                    for (let endNode of nodes[startNode]) {
                        if(tmpSubtree & (1 << (endNode - 1))) {
                            count = Math.max(count, dfs(endNode, max) + 1);
                        }
                    }
                    return count;
                }

                if(tmpSubtree === 0) {
                    result = tmpVal;
                } else {
                    break;
                }
            }
        }
        if(0 < result) resultArr[result-1]++;
    }

    return resultArr;



};

시간 복잡도는 다음과 같다.

• Permutaion : 2^Node갯수
• Node에서 1만큼의 처리
  • 1이 다 찬 경우 1번 + 1이 한번빠진 경우 Node갯수 - 2번 + 1이 두번 빠진 경우 Node갯수 - 3번 ...
    • 예) 1111 + 4C1(0한개 뽑는 경우) + 4C2(1두개 뽑는 경우)
  • 대략적으로 = n^2

O(2^N * N^2) 가 시간 복잡도가 된다.

쫌 시간 복잡도 N^2가 찜찜하긴 한데 이정도 일듯 하다.