[JavaScript] 트리 데이터 구조 변환 시 무한 루프 방지하기

Backgrounds

현제 개발 중인 서비스에서는 하나의 가이드 속 다양한 단계(Step)를 표현하기 위해 트리 구조의 데이터를 생성하고 관리하고 있습니다.

각 Step은 수행할 작업, 다음 단계(next step)를 포함하는 형태로, 이를 통해 트리 구조를 생성하고 탐색할 수 있습니다.

 

이때 이러한 자료 구조 형태를 FE에서 UI로 표현해야 했습니다.

물론 이런 UI는 아니었습니다

BackEnd에서는 Step 목록을 단순히 가이드 하위에 존재하는 Step 배열로 반환해주고 있었고 
이러한 배열 형태로는 각 node들 간의 부모-자식 관계를 나타낼 수 없었습니다. (index가 순서가 아니니까요)

 

따라서 FE 측에서 tree형태 UI로 나타낼 수 있도록 입력받은 node 배열을 변환해줘야 했습니다.

요구 사항을 좀 더 구체적으로 얘기해 보면...

1. 데이터 배열을 입력받아, 해당 tree 구조의 root node를 찾아 반환한다.
(이때 root node는, '다음 node id'가 아무도 자신을 가리키지 않는 node를 의미)
2. 변환된 root node는 children이라는 속성을 갖는다.
3. children에는 '다음 node id'와 일치하는 node 배열이 존재한다.
4. 반환된 node들에는 depth라는 속성이 추가되며, tree 구조에서 해당 node의 깊이 를 의미한다.

 

즉 root node를 찾은 후, children을 순회하며 자기 자신의 자식 node들을 재귀적으로 보여주면

→ tree 형태 자료 구조를 시각적으로 표현할 수 있겠죠!

 

interface NodeInput {
  id: string;
  name: string;
  actionList?: { nextNodeId: string }[];
}

interface TreeNode extends NodeInput {
  depth: number;
  children: TreeNode[];
}

export function createRootTreeNode(data: NodeInput[]): TreeNode | null {
  const dataMap = new Map<string, TreeNode>();

  // 모든 데이터 항목을 맵에 저장하고 depth와 children 속성을 추가
  data.forEach((item) => {
    dataMap.set(item.id, {
      ...item,
      children: [],
      depth: -1, // 초기 depth는 -1로 설정하여 나중에 계산
    });
  });

  let rootNode: TreeNode | null = null;

  // 데이터를 순회하며 트리 구조를 생성
  data.forEach((item) => {
    const node = dataMap.get(item.id);
    if (!node) return;

    // 자식 노드를 추가
    if (item.actionList) {
      item.actionList.forEach((action) => {
        if (action.nextNodeId) {
          const childNode = dataMap.get(action.nextNodeId);
          if (childNode) {
            node.children?.push(childNode);
          }
        }
      });
    }

    // 자신을 가리키는 액션이 없는 경우 루트 노드로 설정
    const hasParent = data.some((dataItem) =>
      dataItem.actionList?.some((action) => action.nextNodeId === item.id)
    );

    if (!hasParent) {
      rootNode = node;
    }
  });

  // 루트 노드에서 깊이 계산 시작
  if (rootNode) {
    calculateDepthBFS(rootNode, 0);
  }

  return rootNode;
}

// 너비 우선 탐색을 통해 깊이 계산
function calculateDepthBFS(root: TreeNode, startDepth: number): void {
  const queue: TreeNode[] = [root];
  root.depth = startDepth;

  while (queue.length > 0) {
    const currentNode = queue.shift();
    if (!currentNode) {
      continue; // queue가 비어있으면 continue로 넘어감
    }
    const currentDepth = currentNode.depth;
    currentNode.children.forEach((child) => {
      child.depth = currentDepth + 1;
      queue.push(child);
    });
  }
}

 

createRootTreeNode 함수를 만들어, 입력된 배열 속 모든 Step들을 순회하며 children을 지정해 준 모습! 

추가적으로 변환된 root node에서부터 하위 children속 자식 node들을 순회하며 depth도 추가해 줬습니다. (calculateDepthBFS)

 

 

Problems

트리 구조로 생성된 데이터에서는 위 코드가 문제없이 동작했습니다.

 

하지만 데이터 이관 과정에서 오류가 발생해,

자식 노드가 다시 부모 노드들 중 하나를 가리키는 그래프 형태의 데이터가 생성되고 말았습니다!

 

이로 인해 애플리케이션이 무한 루프에 빠져 영문도 모르게 강제 종료되는 문제가 발생했죠.

// queue를 이용한 너비 우선 탐색
function calculateDepthBFS(root: StepNode, startDepth: number): void {
  const queue: StepNode[] = [root];
  root.depth = startDepth;

  while (queue.length > 0) {
    const currentNode = queue.shift();
    if (!currentNode) {
      continue; // queue가 비어있으면 continue로 넘어감
    }
    const currentDepth = currentNode.depth;
    // children에 자기 자신 OR 자신의 부모 노드가 존재할 경우, 무한 루프 발생
    currentNode.children?.forEach((child) => {
      child.depth = currentDepth + 1;
      queue.push(child);
    });
  }
}

 

원인은 depth를 지정하기 위해 작성한, 위 함수 때문이었습니다.

BFS 알고리즘을 사용해, root node에서부터 바로 자식 노드들을 하나씩 방문해 depth를 지정해주고 있었는데...

graph 형태의 자료구조에서는 children에 자기 자신 OR 자신의 부모 노드가 존재하게 되고,

이로 인해 queue에 계속해서 순회할 node가 존재해 무한 루프에 빠지고 만 것이죠.

 

Solutions

자료 구조 시간에 배운 것처럼 각 노드들을 한 번만 방문하면, 순환 참조 node가 생겨나지 않겠죠!

 

즉 방문한 노드를 추적하는 visited 집합(Set)을 사용해 한 번도 방문하지 않은 node인 경우에만 자식 node로 추가해 줄 수 있습니다.

interface NodeInput {
  id: string;
  name: string;
  actionList?: { nextNodeId: string }[];
}

interface TreeNode extends NodeInput {
  depth: number;
  children: TreeNode[];
}

export function createRootTreeNode(data: NodeInput[]): TreeNode | null {
  const dataMap = new Map<string, TreeNode>();
  const visited = new Set<string>(); // 방문한 노드를 추적하는 집합

  // 모든 데이터 항목을 맵에 저장하고 depth와 children 속성을 추가
  data.forEach((item) => {
    dataMap.set(item.id, {
      ...item,
      children: [],
      depth: -1, // 초기 depth는 -1로 설정하여 나중에 계산
    });
  });

  let rootNode: TreeNode | null = null;

  // 데이터를 순회하며 트리 구조를 생성
  data.forEach((item) => {
    const node = dataMap.get(item.id);
    if (!node) return;

    // 자식 노드를 추가
    if (item.actionList) {
      item.actionList.forEach((action) => {
        // 방문하지 않은 노드만 처리
        if (action.nextNodeId && !visited.has(action.nextNodeId)) {
          const childNode = dataMap.get(action.nextNodeId);
          if (childNode) {
            node.children.push(childNode);
          }
          visited.add(action.nextNodeId); // 노드를 방문한 것으로 표시
        }
      });
    }

    // 자신을 가리키는 액션이 없는 경우 루트 노드로 설정
    const hasParent = data.some((dataItem) =>
      dataItem.actionList?.some((action) => action.nextNodeId === item.id)
    );

    if (!hasParent) {
      rootNode = node;
    }
  });

  // 루트 노드에서 깊이 계산 시작
  if (rootNode) {
    calculateDepthBFS(rootNode, 0);
  }

  return rootNode;
}

// 너비 우선 탐색을 통해 깊이 계산
function calculateDepthBFS(root: TreeNode, startDepth: number): void {
  const queue: TreeNode[] = [root];
  root.depth = startDepth;

  while (queue.length > 0) {
    const currentNode = queue.shift();
    if (!currentNode) {
      continue; // queue가 비어있으면 continue로 넘어감
    }
    const currentDepth = currentNode.depth;
    currentNode.children.forEach((child) => {
      child.depth = currentDepth + 1;
      queue.push(child);
    });
  }
}

 

createRootTreeNode 함수는 자식 노드를 추가할 때, 방문하지 않은 노드만 children으로 추가하도록 수정했습니다.

 

방문 후에는 visited 집합에 추가해, 자식 노드가 두 개 이상의 부모 노드를 갖지 않도록 강제했고

이를 통해 tree가 아닌 graph 형태의 데이터가 입력된 예외 상황에서도 안전하게 데이터를 변환할 수 있었습니다.