본 포스팅은 실제 프로젝트에서 워크플로우의 테스트케이스 작성 시 겪게된 어려움을 해결하기 위해 시도해 봤던 내용을 공유하는 내용입니다. 시도해본 내용이니만큼 더 효율적인 디자인 패턴이나 방식이 있을 수 있을 수 있습니다.

워크플로우를 통해 복잡한 비즈니스 로직을 도식화 하는 경우에, 해당 워크플로우를 검증하기 위한 테스트케이스 추출과정은 복잡도가 올라감에 따라 수작업으로 처리하기에는 정확도와 효율이 매우 떨어지는 경향이 있습니다.

깊이 우선 탐색(DFS) 알고리즘을 통해 복잡한 워크플로우의 모든 경우의 수를 추출하고 해당 워크플로우를 검증하기 위한 테스트케이스를 확인하기 위한 방법으로 DFS 알고리즘을 활용하는 방법을 시도하게 되었습니다.

워크플로우

#

워크플로우 기능이란

#

워크플로우 기능은 업무 프로세스를 자동화하고 최적화하는 도구로, 작업의 순서와 규칙에 따라 작업을 효율적으로 조정합니다. 이는 업무의 이동, 승인, 통지 등의 단계를 자동으로 실행하며, 업무 흐름을 직관적으로 만들어 업무 프로세스의 효율성, 일관성 및 직관성 향상에 기여할 수 있습니다.

워크플로우 작성 시 모든 경우의 수

#

워크플로우는 시작과 끝이 정해져있고 유량이 1인 그래프 형태를 갖추고 있습니다.

이러한 그래프 구조에서 시작 노드부터 종료 노드까지의 모든 가능한 경로를 추출하기 위해서는 그래프 탐색 알고리즘인 깊이 우선 탐색 알고리즘을 활용할 수 있을 것이란 가정으로 워크플로우의 모든 경우의 수 추출에 DFS 알고리즘을 적용해보고자 합니다.

그래프 탐색

#

깊이 우선 탐색(DFS, Depth-First Search)이란

#

DFS는 그래프나 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나로, 특정 경로를 따라 최대한 깊이 들어가면서 탐색을 수행하는 방식입니다. 이를 통해 모든 가능한 경로를 탐색할 수 있으며 이를 기반으로 워크플로우의 테스트 케이스를 작성하고자 합니다.

너비 우선 탐색(BFS, Breadth-First Search)이란

#

그래프 너비 우선 탐색(BFS)은 시작 노드에서 인접한 모든 노드를 우선적으로 방문하는 탐색 알고리즘입니다.

시작 노드에서 인접한 노드를 모두 방문한 후, 해당 노드들의 인접 노드들을 차례로 방문합니다.

이 과정은 목표 노드가 발견될 때까지 반복되며, 최단 경로를 찾거나 특정 노드를 찾는 데 사용됩니다

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 차이

#

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)은 그래프를 탐색하는 두 가지 주요 알고리즘입니다. DFS는 한 경로를 끝까지 탐색한 후 다른 경로를 찾아나가며 깊게 들어가는 방식으로 동작합니다.

반면에 BFS는 시작 노드에서 인접한 노드들을 우선적으로 모두 탐색하며, 레벨 단위로 퍼져나가는 방식으로 동작합니다.

DFS는 스택(Stack)이나 재귀를 사용하여 구현되며, BFS는 큐(Queue)를 활용하여 각각 특화된 특징을 갖습니다.

따라서, DFS는 깊은 부분을 우선적으로 탐색하고자 할 때, BFS는 넓은 영역을 우선적으로 탐색하고자 할 때 주로 사용됩니다.

워크플로우는 시작과 끝 노드가 정해진 그래프 이며 워크플로우의 테스트 케이스를 추출하기 위한 목적으로는 깊이 우선 탐색을 통해 모든 경우를 따지는 것이 효율적이라 생각되어 DFS 알고리즘을 통해 경우의 수를 계산을 시도합니다.

깊이 우선 탐색(DFS)의 동작 방법

#

깊이 우선 탐색(DFS)은 아래와 같은 순서로 동작합니다.

1. 시작 노드 선택

   • 탐색을 시작할 노드를 선택합니다.

2. 노드 방문 표시

   • 시작 노드를 방문했다고 표시하고, 해당 노드를 스택(Stack)이나 재귀 호출의 기록에 추가합니다.

3. 인접 노드 탐색

   • 현재 방문한 노드의 인접 노드 중에서 아직 방문하지 않은 노드를 찾습니다.

4. 깊게 들어가기

   • 방문하지 않은 인접 노드가 있다면, 해당 노드를 선택하고 1~3단계를 반복합니다. 선택한 노드를 방문 표시하고, 스택이나 재귀 호출의 기록에 추가합니다.

5. 탐색 불가 시 되돌아감

   • 더 이상 방문하지 않은 인접 노드가 없다면, 이전 단계로 돌아가서 이전 노드로 되돌아갑니다. 이때 스택이나 재귀 호출에서 이전 노드를 꺼내고, 해당 노드의 인접 노드 중 아직 방문하지 않은 노드를 찾아 다시 깊이 우선 탐색을 수행합니다.

6. 모든 노드를 방문할 때까지 반복

   • 스택이 비거나 모든 노드를 방문할 때까지 위 과정을 반복하여 그래프를 완전히 탐색합니다.

   

   [이미지 출처: PPT - Depth-first search PowerPoint Presentation, free download - ID:8160117 (slideserve.com)]

깊이 우선 탐색(DFS) 적용 아이디어

#

위의 깊이 우선 탐색(DFS)은 동작 시 시작노드에서 종료노드까지 도달한 경우의, 스택에 저장되어있는 경로를 하나의 테스트 케이스로 간주할 수 있습니다.

재귀 호출을 통한 작업을 통해 각각 하나하나의 테스트 케이스를 취합해 모든 경우의 수를 얻을 수 있을거라 예상됩니다.

다음 포스팅에서는 간단한 비지니스 로직으로 워크플로우를 작성하고, 깊이 우선 탐색(DFS)를 적용하여 작성한 워크플로우의 테스트 케이스를 추출해보도록 하겠습니다.