[Algorithm] 복잡한 DOM 예제로 보는 DFS 탐색 알고리즘

목표

---

아래 DOM 구조에서 가장 안쪽 요소부터 시작해 부모 요소로 갈 수록 중첩 레벨이 1씩 늘어나고, class에 대응하는 dataset에 중첩 레벨 값을 할당해야 한다. 예를들어 class가 "clause" 이고, 해당 요소의 중첩 레벨이 2라면 data-clause-lv="2" 속성을 할당한다.

<p ref="{ref}">
  <span class="clause" data-clause-lv="2">
    <span class="word" data-word-lv="1">
      <span data-index="0">Hello</span>
    </span>
  </span>
</p>;

 

만약 자식 요소가 2개 이상일 땐 자식 요소들중 중첩 레벨이 가장 높은 값 + 1이 부모 요소의 중첩 레벨이 된다. 아래 예시를 기준으로 1번째 자식의 중첩 레벨(data-word-lv="1") 보다, 2번째 자식의 중첩 레벨(data-phrase-lv="2")이 더 높으므로, 부모 요소의 중첩레벨은 3이 된다(data-clause-lv="3").

<p ref="{ref}">
  <span class="clause" data-clause-lv="3"> <!-- 부모 -->
    <span class="word" data-word-lv="1"> <!-- 자식 1 -->
      <span data-index="0">Hello</span>
    </span>
    <span class="phrase" data-phrase-lv="2"> <!-- 자식 2 -->
      <span class="word" data-word-lv="1">
        <span data-index="1">World</span>
      </span>
    </span>
  </span>
</p>

 

예제

---

0~13은 토큰 인덱스

영어 문장에서 단어 혹은 문장부호를 인덱스 기준으로 잡고(토큰 인덱스), 그 토큰들이 서로 어떻게 연결되어 문장을 구성하는지에 대한 정보를 중첩 구조로 표현하면 아래와 같은 DOM 구조를 갖는다. 이제 아래 DOM 구조에서 ?로 표시된 중첩 깊이를 계산해야 한다.

<p class="text-xl">
  <span data-index="0">I</span>
  <span data-index="1">am</span>
  <span class="kc phrase" data-phrase-lv="?">
    <span data-index="2">a</span>
    <span data-index="3">boy</span>
    <span class="kc clause" data-clause-lv="?">
      <span data-index="4">who</span>
      <span data-index="5">likes</span>
      <span class="kc phrase" data-phrase-lv="?">
        <span class="kc phrase" data-phrase-lv="?">
          <span data-index="6">to</span>
          <span class="kc word" data-word-lv="?">
            <span class="kc word" data-word-lv="?">
              <span class="kc word" data-word-lv="?">
                <span data-index="7">play</span>
              </span>
            </span>
          </span>
          <span data-index="8">tennis</span>
        </span>
        <span class="kc clause" data-clause-lv="?">
          <span data-index="9">which</span>
          <span data-index="10">is</span>
          <span class="kc word" data-word-lv="?">
            <span class="kc word" data-word-lv="?">
              <span data-index="11">fun</span>
            </span>
          </span>
          <span data-index="12">.</span>
        </span>
      </span>
    </span>
  </span>
</p>

 

구현

---

DFS 노드 방문 순서(검정 배경 숫자) 및 각 노드 반환값(점선 화살표)

assignCalculatedLevel 함수는 자식 요소 중 가장 높은 중첩 레벨을 찾는 것을 목표로 한다. 이를 위해 자식 요소가 있을 때마다 자신을 재귀적으로 호출하는 DFS 방식으로 탐색하여 가장 안쪽 요소부터 계산해 나간다.

 

이 과정에서 word, phrase, clause 클래스를 가진 요소에 대해선 해당 중첩 레벨 정보를 data- 속성에 할당한다. 이렇게 각 요소의 최대 중첩 레벨이 결정되면 그 값을 반환하여 상위 요소의 중첩 레벨 계산에 활용한다.

const assignCalculatedLevel = (element: HTMLElement) => {
  // element 자식 요소중 가장 높은 레벨을 저장할 변수
  let maxChildLevel = 0;

  // element의 모든 자식 요소 순회
  for (const child of element.children) {
    // 깊이 우선 탐색 방식으로 자식 요소 레벨 계산
    const childLevel = assignCalculatedLevel(child as HTMLElement);
    // maxChildLevel, childLevel 둘 중 더 큰 값을 maxChildLevel로 지정
    maxChildLevel = Math.max(maxChildLevel, childLevel);
  }

  const hasChild = element.children.length > 0;
  // 현재 element에 자식 요소가 있으면 maxChildLevel + 1 값을 현재 요소의 레벨로 지정
  // 현재 element에 자식 요소가 없으면 maxChildLevel 값을 현재 요소의 레벨로 지정
  const currentLevel = hasChild ? maxChildLevel + 1 : maxChildLevel;

  const classesToCheck: TagType[] = ['word', 'phrase', 'clause'];

  classesToCheck.forEach((className) => {
    // 현재 요소가 classesToCheck 배열에 있는 클래스를 포함하는지 검사
    if (element.classList.contains(className)) {
      // 클래스를 포함하면 해당 클래스에 대한 레벨 정보를 `data-${className}Lv` 속성에 할당
      element.dataset[`${className}Lv`] = `${currentLevel}`;
    }
  });

  // 현재 요소의 레벨 값 반환
  return currentLevel;
};

const calculateNestingLevel = (ref: RefObject<HTMLParagraphElement>) => {
  const spans = ref.current?.children;
  if (!spans) return;

  Array.from(spans).forEach((span) => {
    const spanElement = span as HTMLElement;
    // dataset.kc가 있는 요소에 대해서만 호출
    if (spanElement.dataset.kc) assignCalculatedLevel(spanElement);
  });
};

각 요소에 주석으로 추가한 숫자 소괄호는 가장 안쪽 요소까지 방문한 뒤 리턴하는 순서를 나타낸다

<p class="text-xl"> <!-- calculateNestingLevel 함수 시작 -->
│
├── <span data-index="0">I</span> <!-- skip -->
├── <span data-index="1">am</span> <!-- skip -->
└── <span class="kc phrase" data-phrase-lv="7"> <!-- assignCalculatedLevel 함수 시작 -->
    ├── <span data-index="2">a</span> <!-- return 0 -->
    ├── <span data-index="3">boy</span> <!-- return 0 -->
    └── <span class="kc clause" data-clause-lv="6"> <!-- (13) return 6 -->  
        ├── <span data-index="4">who</span> <!-- return 0 -->
        ├── <span data-index="5">likes</span> <!-- return 0 -->
        └── <span class="kc phrase" data-phrase-lv="5"> <!-- (12) return 5 -->  
            ├── <span class="kc phrase" data-phrase-lv="4"> <!-- (6) return 4 -->
            │   ├── <span data-index="6">to</span> <!-- return 0 -->
            │   ├── <span class="kc word" data-word-lv="3"> <!-- (4) return 3 -->
            │   │   └── <span class="kc word" data-word-lv="2"> <!-- (3) return 2 -->
            │   │       └── <span class="kc word" data-word-lv="1"> <!-- (2) return 1 -->
            │   │           └── <span data-index="7">play</span> <!-- (1) return 0 -->
            │   └── <span data-index="8">tennis</span> <!-- (5) return 0 -->
            └── <span class="kc clause" data-clause-lv="3"> <!-- (11) return 3 -->  
                ├── <span data-index="9">which</span> <!-- return 0 -->
                ├── <span data-index="10">is</span> <!-- return 0 -->
                ├── <span class="kc word" data-word-lv="2"> <!-- (9) return 2 --> 
                │    └── <span class="kc word" data-word-lv="1"> <!-- (8) return 1 --> 
                │        └── <span data-index="11">fun</span> <!-- (7) return 0 -->
                └── <span data-index="12">.</span> <!-- (10) return 0 -->

 

번외

---

word, phrase, clause 중첩 레벨 정보를 해당하는 요소의 data-* 속성에 할당했으므로 레벨 값에 대응하는 높이를 지정할 수 있다. 예를들어 기본 높이가 1rem이면 레벨 1부터 1rem * 1, 1rem * 2,, ... 방식으로 높이를 가질 수 있는 것.

 

SCSS의 @for문을 이용하면 각 레벨에 대한 스타일을 동적으로 생성할 수 있다.

$clause-padding-base: 0.1rem; // 절/구 하단 여백
$clause-top-base: 1.5rem; // 절/구 이름 상단 여백
$clause-offset-base: 1.3rem; // 절/구 점선 상하 간격
$word-top-base: 1.5rem; // 단어 상단 여백
$word-offset-base: 1rem; // 단어 상하 간격

@for $i from 1 through 30 {
  $offset: $clause-offset-base * ($i - 1);

  .kc.clause[data-clause-lv='#{$i}'],
  .kc.phrase[data-phrase-lv='#{$i}'] {
    padding-bottom: $clause-padding-base + $offset;

    &:after {
      top: $clause-padding-base + $clause-top-base + $offset;
    }
  }
}

@for $i from 1 through 30 {
  $offset: $word-offset-base * ($i - 1);

  .kc.word[data-word-lv='#{$i}']:after {
    top: $word-top-base + $offset;
  }
}

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요