[algorithm] 부분집합의 수 구하기

문제

tree의 모든 edge를 담은 2차원 배열이 주어졌을 때 독립된(서로 떨어져있는) 서브트리의 개수 구하라
예를 들어
[[0, 1], [2, 3], [3, 4], [4, 5]]
와 같이 주어진 트리에는 (0-1), (2-3-4-5) 두 개의 독립된 서브트리가 있다.

코드

function numberOfSubTrees(tree) {
  let count = 0;
  const len = tree.length; // 코드에서 자주 쓸 거라서 따로 변수로 만든다.
  let visited = new Array(len).fill(false); // edge 방문 여부를 담을 배열을 만들고 초기값은 false로 설정

  for (let i = 0; i < len; i++) { // 모든 edge를 돌면서
    let queue = []; 
    // 새로운 subtree를 시작하자!
    if (!visited[i]) { 
      // 이미 방문한 엣지는 어딘가에 연결되어 있을 것이므로 패스

      count++; // subtree의 개수도 하나 증가시키자!
      queue.push(tree[i]); 
      // 일단 시작정점이 될 edge를 queue에 넣어준다. 연결된 것들이 있으면 계속해서 쌓일 것이다.
      visited[i] = true; // 방문마크 남기고
    }
    while(queue.length !== 0) {
      // queue에서 edge를 하나씩 꺼내면서 연결된 것들을 다 찾아줄 것인
      // edge가 비면 가능한 모든 엣지가 연결된 상태일 것이다
      const [v1, v2] = queue.shift(); // edge를 하나씩 꺼내 두 정점을 각각의 변수에 담는다.
      for (let j = i + 1; j < len; j++) { 
        // 뒤에 있는 edge들을 쭉 돌면서 현재의 edge에 연결되었는지 확인한다.

        if (!visited[j]) {
          if (tree[j].includes(v1)) { // 연결되었다면
            visited[j] = true; // 방문마크 필수
            queue.push(tree[j]); // queue에 넣어준다.
          }
          if (tree[j].includes(v2)) {
            visited[j] = true; //  여기도 방문마크
            queue.push(tree[j]);
          }
        }
      }
    }
  }

  return count;
}

주요 포인트

queue 자료구조를 쓴 것은 아니다. 위에서 쓰인 변수 queue는 연결된 edge들을 담아두는 배열 역할을 할 뿐이다.