[Algorithm] 데이터 추가, 삭제, 정렬로 보는 BFS / DFS 탐색 알고리즘

예시 데이터

---

Hello 인덱스: 0~1 / World 인덱스: 1~2 / 콤마 인덱스: 2~3, Inchala: 3~4

단어 혹은 문장부호(' 아포스트로피 제외)를 기준으로 분리한 토큰 인덱스 정보가 담기는 Part 객체가 있다. 이 Part 객체는 child 배열을 가지며, child 배열의 각 요소인 Part는 부모 Part의 토큰 인덱스 범위 내의 인덱스를 가진다. 예를들어 부모 Part의 토큰 인덱스 범위가 2~13이라면 자식 Part의 토큰 인덱스는 3~13(3~13, 4~13, ...) 혹은 2~12(2~12, 2~11, ...) 범위를 가진다.

[
  // parts 배열
  {
    id: 0, // part
    begin: 2,
    end: 13,
    kc: [{ id: 'kc-1', /* ... */ }],
    child: [ // parts 배열
      {
        id: 1, // part
        begin: 4,
        end: 13,
        kc: [{ id: 'kc-2', /* ... */ }],
        child: [{ /* ... */ }],
      },
    ],
  },
  {
    // ...
  },
];

 

위와 같은 데이터 구조에서 각 Part의 kc 배열에 있는 특정 요소를 추가/삭제 하는게 목적. 참고로 kc 배열은 begin~end 범위의 문법적 특성을 나타낸다.

 

KC 삭제 | BFS

---

목표

BFS 탐색 순서

현재 레벨에 있는 모든 part의 kc 배열을 탐색하면서 입력받은 kcId를 찾아 삭제한다. 현재 레벨 깊이에서 kcId를 찾지 못하면 다음 레벨 깊이의 part 요소들을 검사하는 너비 우선 탐색 방식 사용.

 

구현

재귀함수 대신 queue로 구현. while 문을 순회할 때마다 queue 가장 앞쪽 요소를 추출한 후 검사. part.kc 배열 내에서 입력받은 kcId를 찾지 못하면 현재 part의 모든 child 요소를 queue에 추가하고 탐색 반복.

const removeKCById = (parts: Array<Part>, kcId: KC['id']) => {
  const newParts: Array<Part> = structuredClone(parts); // 깊은 복사
  const queue = [...newParts]; // 탐색할 parts
  let found = false;

  while (queue.length > 0) {
    const currentPart = queue.shift();

    if (currentPart?.kc.length) {
      // filter 후의 part.kc 배열 길이와 비교하기 위해 원본 kc 배열 길이 임시 저장
      const originalLength = currentPart.kc.length;

      // 입력받은 kc.id를 찾으면 kc 배열에서 제외
      currentPart.kc = currentPart.kc.filter(({ id }) => id !== kcId);

      // originalLength 길이가 더 크면 kc.id를 찾아 삭제했으므로 함수 종료
      if (originalLength > currentPart.kc.length) {
        found = true;
        break;
      }
    }

    // 현재 part.kc 배열에서 입력받은 kc.id를 찾지 못하면 queue에 추가한 후 위 과정 반복
    if (currentPart?.child?.length) queue.push(...currentPart.child);
  }

  if (!found) console.warn(`No KC with id ${kcId} was found.`);

  return newParts;
};

 

KC 추가 | DFS

---

 

목표

문자열의 토큰 인덱스를 나타내는 begin/end와 문법적 특성을 나타내는 kc를 받아, 해당 인덱스 범위와 일치하는 part를 찾아 kc 배열에 추가한다. 일치하는 part를 찾지 못했다면 새로운 part를 생성한다.

begin/end 범위를 포함하지 않는 part의 자식은 탐색할 필요가 없다.

 

예를들어 begin 8, end 9를 인자로 받았을 때 해당 인덱스 범위를 포함하는, begin 보다 작거나 같고 end 보다 크거나 같은 part를 깊이 우선 방식으로 탐색해 나가야 한다(위 이미지 왼쪽 케이스 참고).

 

구현

const addKCToPart = (parts: Part[], begin: number, end: number, kc: KC) => {
  const newParts: Array<Part> = structuredClone(parts); // 깊은 복사

  for (const part of newParts) {
    // begin, end 범위와 정확히 일치한다면 part.kc 배열에 추가한 후 함수 종료
    if (part.begin === begin && part.end === end) {
      part.kc.push(kc);
      return newParts;
    }

    // begin 보다 작거나 같고, end보다 크거나 같으면 범위내에 있으므로 자식 part 탐색
    if (part.begin <= begin && part.end >= end) {
      // 자식 part 재귀적으로 탐색
      part.child = addKCToPart(part.child, begin, end, kc);
      return newParts;
    }
  }

  /** 매칭하는 part 없으면 새로운 part 생성 */
  newParts.push({
    id: uuidv4(),
    begin,
    end,
    kc: [kc],
    child: [],
  });

  return newParts;
};

새로운 노드(Part)를 추가하고 해당 범위내 다른 노드를 자식으로 옮기는 심화 버전 ▼

const cloneParts = (parts: Part[]): Part[] => structuredClone(parts);

const moveToPart = (parts: Part[], begin: number, end: number): Part[] => {
  // flatMap은 1depth까지 배열을 펼치고, 빈 배열을 반환하면 결과에 포함하지 않음
  return parts.flatMap((part) => {
    if (
      (part.begin > begin && part.end <= end) ||
      (part.begin >= begin && part.end < end)
    )
      return [part];
    else return moveToPart(part.child, begin, end);
  });
};

export const addKCToPart = (
  parts: Part[],
  begin: number,
  end: number,
  kc: KC,
): Part[] => {
  const newParts = cloneParts(parts);

  for (const part of newParts) {
    if (part.begin === begin && part.end === end) {
      part.kc.push(kc);
      return newParts;
    }

    if (part.begin <= begin && part.end >= end) {
      part.child = addKCToPart(part.child, begin, end, kc, onInvalidCallback);
      return newParts;
    }
  }

  if (newParts.length === 0) return [getNewPart(begin, end, [kc])];

  const left = getNewPart(begin, end, [kc]);
  const right = getNewPart(end, newParts[newParts.length - 1].end);

  left.child = moveToPart(newParts, left.begin, left.end);
  right.child = moveToPart(newParts, right.begin, right.end);

  return [left, right];
};

 

Empty Part 삭제 | DFS

---

DFS 탐색 순서

part.kc와 part.child 길이가 모두 0이면 더이상 사용하지 않는 part이므로 삭제해야 한다. 모든 노드를 방문해서 확인해야 하므로 DFS, BFS 어떤 것을 사용해도 무방하다. part.child 길이가 1이상이면 사용하는 part로 판단하므로, 가장 깊은 노드가 비어있을 가능성이 많다. 따라서 깊이 우선 탐색으로 구현한다.

const removeEmptyKCParts = (parts: Part[]) => {
  return parts.reduce((acc: Part[], part: Part) => {
    // 깊이 우선 탐색을 위해 child가 있다면 child 재귀호출
    if (part.child.length) part.child = removeEmptyKCParts(part.child);

    // 현재 part의 사용 여부에 대한 조건
    if (part.kc.length || part.child.length) {
      acc.push(part);
    }

    return acc;
  }, []);
};

 

Parts 정렬 | DFS

---

DFS 탐색 순서

parts 배열에서 가장 넓은 범위의 인덱스를 가지는 part가 배열 앞쪽에 오도록 내림차순 정렬한다. begin + end 합이 클 수록 더 넓은 범위를 가진다고 볼 수 있다. 정렬 후엔 각 part를 순회하면서 child 배열(parts) 길이가 1 이상인지 검사하고, 참이면 재귀호출해서 자식 parts 배열도 정렬하는 과정을 반복한다.

const sortParts = (parts: Part[]) => {
  return parts
    .sort((a, b) => b.begin + b.end - (a.begin + a.end))
    .map((part) => {
      if (part.child.length) part.child = sortParts(part.child);
      return part;
    });
};