DFS

graph TD
    A -->|1| B
    B -->|2| D["D (리프 노드 도착 3)"]
    D -.-|"백트래킹(4)"| B
    B -->|5| E["E (리프 노드 도착 6)"]
    E -.-|"백트래킹(7)"| B
    B -.-|"백트래킹(8)"| A
    A -->|9| C
    C -->|10| F["F (리프 노드 도착 11)"]
    F -.-|"백트래킹(12)"| C
    C -->|13| G["G (리프 노드 도착 14)"]
    G -.-|"백트래킹(15)"| C

TLDR

• 탐색 목적에 적합한 방문과 순회 방식, 조회 시점을 구성한다.

• 조건은 조회, 백트래킹에 적용될 수 있다.

Prologue

이전 글들을 바탕으로 DFS를 방문, 조회, 백트래킹, 순회 개념으로 이해하기 위해 작성했다.

1. 그래프의 구조(링크)

2. 그래프의 탐색(링크)

글을 쓰고 나서 보니, 이전보다 더 이해가 깊어진 것 같다. "모든 유형의 DFS를 외워서 풀어야지"가 얼마나 바보같은 방법인 지 새삼 느껴졌다.

(TMI: 학습 과정에서 느낀 점 - 넘겨도 됩니다.)

그래프, 자료 구조 공부하면서 특히 재밌었다. 왠지 모르게 철학적인 느낌이 든다(?). 이런 걸 재밌다고 생각하는 게 큰 변화로 느껴진다. 자료 구조, 알고리즘 공부는 현실적인 이유로 시작했다. 채용에서 요구되고, 코딩 테스트를 통과해야 하니까. 근데 사실 학습 효율도 떨어졌고, 재미도 없었다. 무수한 삽질과 망각, 여전히 미진한 실력으로 좌절도 여러 번 했다. 그러나 이제는 별로 상관 없다. 그저 계속 필요한 학습을 이어갈 수 있다.

1. 기본 개념

1-1. 방문과 조회

DFS(깊이 우선 탐색) 알고리즘은 목적에 따라 방문과 조회 순서를 결정해야 한다. 이에 따라서 구체적인 함수 구성이 크게 달라질 수 있다.

방문(Visit): 새로운 노드로 이동하는 과정

• 대부분의 경우 visited라는 변수로 방문 여부를 기록해야 한다.

• 방문 여부 확인과 업데이트는 전체 로직에 중요한 영향을 끼친다.

• 방문 순서 = 순회 방식은 주어진 문제마다 달라질 수 있다.

• 목적에 따라 방문과 조회가 함께 이루어지거나, 그렇지 않을 수 있다.

조회(Query): 현재 노드의 데이터를 확인하는 과정

• 대부분의 경우 조건에 따라 노드 데이터를 판별해야 한다.

• 노드 데이터를 기반으로 데이터를 가공할 때가 많다.

• ex) 노드 데이터가 1인 노드들의 연결 관계, 경로, 노드 데이터를 바탕의 탐색 등

핵심은 방문과 조회의 순서를 주어진 문제에 맞게 구성하는 것이다. 하지만 매번 다른 모습의 DFS 함수를 떠올리기는 쉽지 않다. 그래서 기본 원리를 제대로 알아야 한다.

DFS는 가장 깊이 있는 노드까지 탐색한 후, 더 이상 탐색할 노드가 없으면 백트래킹(되돌아가기)한다. 모든 DFS는 탐색 순서의 메커니즘을 스택Stack으로 구현한다.

JS에서 스택은 기본적이다.

1. 콜 스택(재귀 함수): JS에서 함수 실행 순서는 스택으로 관리된다. 가장 나중에 호출된 함수부터 실행된다.

2. 명시적인 스택 : 배열로 스택을 만들 수 있다. push, pop 메서드로 스택을 쉽게 관리할 수 있다.

재귀 함수를 사용하느냐, 스택을 명시하느냐에 따라 방문과 조회의 순서를 조정할 수 있다. 일반적으로 재귀 함수는 전위 순회를 따른다.

1-2. 백트래킹과 순회

백트래킹(Backtracking): 탐색을 진행하다가 더 이상 탐색할 노드가 없으면 이전 노드로 되돌아가는 과정
순회(Traversal): 그래프의 노드를 일정한 순서로 방문하는 것. 그래프 전체의 탐색 순서 방식과 연관된다.

두 개념은 방문과 조회, 더 구체적으로 둘이 이루어지는 타이밍과 연관이 깊다. 이 부분에서 각 DFS 함수의 형태가 결정되기 때문이다.

DFS는 재귀 함수와 배열 스택으로 구현할 수 있다. 코드의 가독성, 성능 등에 다소 차이가 생길 수 있으나 적절한 형태를 선택하면 함수 구성이 쉬워진다.

• 재귀 함수: 전위 순회를 기본으로 한다. 백트래킹, 순회 방식은 모두 '가장 깊은 노드'의 서브 트리를 따라간다.

• 배열 스택(명시적 스택): 함수 내부에 스택 변수를 만들고, pop, push 메서드로 순서를 관리한다. 스택에 먼저 추가된 노드가 나중에 실행된다.

함수 콜스택 쌓이는 것 = 방문이 먼저 일어난 순서대로
A > B > C 순서대로 (재귀) 함수 호출이 콜 스택에 쌓인다
			|__C__|
			|__B__|
			|__A__|

함수가 실행되는 순서 = 가장 마지막에 추가된 노드 = 가장 깊은 노드, 리프 부터
			|_____|
			|__B__|
C 실행		|__A__|
C > B > A 순서로 함수가 실행된다.

2. 기본적 구현

아래는 재귀 함수로 구현된 기본적인 DFS 구현체이다.

function dfs(graph, node, target, visited = new Set()) {
    // dfs의 기본 백트래킹
    if (visited.has(node)) {
        return; // 이미 방문한 노드라면 탐색 중단
    }
    visited.add(node); // 현재 노드의 방문 처리

	// 그래프[현재 노드 인덱스]로 인접한 노드를 가져온다.
    const neighbors = graph[node];
	// graph[node]는 보통 인접 노드 인덱스를 배열로 나타낸다.
	// 인접 노드를 얻기 위한 추가 로직이 필요할 수 있다.

	// 여기서 인접 노드를 콜 스택에 차례로 쌓는다
    for (let neighbor of neighbors) {
    // 가장 깊은 노드가 재귀 함수를 통해 마지막 콜 스택에 위치하게 된다.
        dfsExample(graph, neighbor, target, visited);   
    }
    return 
}

3. 구현과 원리

JS로 DFS의 방문, 조회, 순회, 백트래킹의 각 부분을 어떻게 구성할 지 알아보자.

3-1. 방문하기(Visit)

1. 방문 여부를 기록하기

2. 방문 여부를 업데이트하기

방문할 때 중요한 요소는 해당 요소의 방문 여부이다. 이를 통해 탐색이 무한루프에 빠지지 않게 만들 수 있고, 백트래킹도 할 수 있다. 방문 여부는 주어진 데이터에 따라 적절한 형태로 구성할 수 있다.

방문에서 중요한 것은 방문 여부를 선언하는 위치와 방문 여부의 업데이트 타이밍이다. 이로 인해 DFS 탐색 자체가 오류에 빠질 수 있다.

재귀함수와 배열 스택은 방문 여부를 확인하는 것에 다소 차이가 있다. 그러나 인접 노드를 방문하기 전에, 즉 다음 노드를 스택에 추가하기 전에 현재 노드 방문 여부를 true로 설정하는 순서는 동일하다. (이 부분에서 자주 실수했었다.)

재귀 함수: 보통 방문 여부를 나타내는 데이터는 함수 밖에서 선언된다. 재귀함수에서 저장으로 쓸 수 있는 값은 반환 값 혹은 함수 매개 변수와 외부 변수이기 때문이다.

// 재귀함수는 콜스택에 추가되면서 매개변수의 값을 업데이트한다.
function recursiveDfs(graph, node, visited = new Set()) {
    // 이미 방문한 노드를 분기해 무한 루프를 방지하기 위한 중단점이 된다.
    if (visited.has(node)) {
    // 중단되기 전에 로직이 추가될 수 있다.
	    return 
        // 혹은 return false 등 반환값과 함께 함수를 종료할 수 있다.
    }
    // 재귀함수에서는 다음 노드로 이동하기 전에 현재 노드의 방문 여부를 업데이트 해야한다.
    visited.add(node); // ✅ 올바른 타이밍: 인접 노드 방문 전에 업데이트 해야한다
    // 다음 노드로 이동한다.
    for (let neighbor of graph[node]) {
    // 콜 스택에 다음 노드를 추가한다
        dfs(graph, neighbor, visited); // neighbor는 현재 노드 node와 연결돤 노드들이다.
        // graph[node]에 정렬된 순서대로 콜 스택에 쌓인다.
        // 가장 마지막에 추가된 노드가 가장 먼저 실행된다.
    }
	visited.add(node); // ❌ 잘못된 타이밍: 인접 노드 방문 후에 업데이트
}

명시적인 스택: 반면에 배열 스택과 반복문은 방문 여부를 DFS 함수 내부에서도 선언할 수 있다.

// 명시적인 스택 함수:
function stackDfs(graph, start) {
	const visited = new Set(); // 방문 여부를 기록하는 Set
	const stack = [start]; // 탐색 시작 노드를 스택에 추가

	while (stack.length > 0) {
		const currentNode = stack.pop(); // 스택에서 노드를 꺼냄
		if (visited.has(currentNode)) {
			continue; // 이미 방문한 노드라면 건너뜀
		}
		visited.add(currentNode); // ✅ 올바른 타이밍: 방문 전에 업데이트 해야한다

		for (let neighbor of graph[currentNode]) {
			stack.push(neighbor); // 인접한 노드를 스택에 추가
            // stack에는 연결된 노드가 graph[currentNode]에 정렬된 순서대로 쌓인다.
            // 마찬가지로 가장 마지막에 추가된 노드 순서대로 while 반복문이 실행된다.
		}
		visited.add(node); // ❌ 잘못된 타이밍: 인접 노드 방문 후에 업데이트
	}
}

특히 방문 여부를 업데이트하는 타이밍은 순회 방식과도 연계되기 때문에, 이 부분의 실수는 탐색 자체를 오류에 빠뜨릴 수 있다.

3-2. 조회(Query)

조회는 특정 조건을 만족하는 노드를 찾기 위해 데이터 확인을 수행하는 단계다. 이 데이터를 바탕으로 탐색 목적과 관련된 작업을 한다.

탐색 목적은 크게 두가지로 분류된다.

1. 특정 노드를 발견하기

2. 그래프를 순회하며 노드 데이터를 수집하기

이를 위해 조회 단계에서 할 일들은 다음과 같다:

1. 조건 판별

   • 노드 데이터를 바탕으로 탐색을 중단할지 결정한다. (ex: 노드 데이터가 1이면 true를 반환한다)

   • 조건이 탐색 경로를 변경하거나 중단할 수 있다. (ex: 현재 노드 인덱스의 데이터가 1이면 인접 노드는 방문하지 않는다)

2. 데이터 가공

   • 조건 판별을 위해 노드 데이터를 가공한다. (ex: 노드 데이터가 1이면 true를 반환한다)

   • 노드 데이터에 의존한 데이터를 바탕으로 결과를 반환한다.

     • ex: 노드 데이터가 1이면 결과에 추가한다. result.push(node) 혹은 count++ 등 다양한 형태가 될 수 있다.

두 가지 모두 노드 데이터에 의존하는 작업이며, DFS 구현은 이 두 가지 작업을 어떻게 처리할지에 달려있다.

조회는 방문과 함께 이루어지는 경우가 많지만, 방문과 조회의 순서는 문제에 따라 다르다. 또한 조회하여 꺼낸 노드 데이터가 탐색 순서에도 영향을 줄 수 있다. 마찬가지로 조회 순서와 노드 데이터로 필요한 값을 가공하는 시점이 중요하다.

// 노드에서 언제 값을 꺼내느냐 = 조회 타이밍이 문제마다 다를 수 있다.

function dfsExample(graph, node, target, visited = new Set()) {
    // dfs의 기본 백트래킹
    if (visited.has(node)) {
        return; // 이미 방문한 노드라면 탐색 중단
        // false를 반환하여 특정 노드 데이터를 찾지 못함을 나타낼 수 있다.
    }
    visited.add(node);

    // A. 특정 노드 데이터를 찾는 경우(노드 데이터 = 타겟일 때 탐색 중단)
    if (node === target) {
        return true; // A 목표 노드를 찾아서 탐색을 중단함
    }
    

    // A2. 현재 노드 데이터가 조건에 해당하지 않으면 백트래킹할 수 있다.
    if (!isValid(node)) {
    // 인접 노드를 방문하지 않고 dfs를 중단한다. 
    // dfs의 기본적인 백트래킹 방식이다.
        return 
        // 위의 visited.has 조건문과 같은 이유로 false를 반환할 수 있다.
    }



	// graph[node]는 보통 인접 노드 인덱스를 배열로 나타낸다.
    const neighbors = graph[node]; // 인접 노드 인덱스를 가져온다.
	// neighbors는 현재 노드의 인접 노드 인덱스들이다. 
    
    // B. 노드 데이터를 바탕으로 값을 계산해야할 때
    // 하지만 graph[node]가 다른 데이터를 의미할 수 도 있다.
    // ex) graph[0] = [ (node의 고유 데이터), 인접 노드 인덱스] 
    // graph[node]에 있는 노드 데이터에 따라 조회한 데이터 로직이 달라질 수 있다.
    
    // 보통 재귀함수로 만든 dfs는 매개변수, 반환값 혹은 외부 변수로 값을 전달한다.
    // 외부 변수에 값을 추가하거나, 매개 변수에 값을 변경한다.
    result.push(processNodeData(node)); // 노드 데이터를 가공하여 결과에 추가
    // count가 dfs의 매개변수
     count += node // 혹은 graph[node] 
	 // 혹은 조회한 노드 데이터에 조건에 따라 저장할 수 있다.
	 if(graph[node] === 1){
		 result.push(node)
	 }


	// 여기서 인접 노드 방문이 이루어진다.
    for (let neighbor of neighbors) {
        dfsExample(graph, neighbor, target, visited);
        // 혹은 dfsExample이 boolean을 반환한다면 
        if (dfsExample(graph, neighbor, target, visited)) {
            return true; // A. 목표 노드를 찾으면 탐색 중단이 가능하다
        }
        
    }
    return false; // A. 목표 노드를 찾지 못한 경우
}

3-3. 백트래킹(Backtracking)

1. 다른 경로에서 같은 노드에 접근할 때마다 달라지는 경우

   • 조합, 순열

2. 모든 경로 찾기

DFS에서 백트래킹은 기본적으로 이루어진다. 앞서 본 dfsExample 의 백트래킹은 visited.has(node)와 !isValid(node)일 때 인접 노드 방문을 중단하여 이루어졌다. 하지만 백트래킹을 다르게 구성해야할 때도 있다.

      ¹8    ¹~⁷은 노드 인덱스이다
     /   \
    ²4    ³2
   / \    / \
  ⁴2  ⁵6 ⁶0 ⁷4  

경로 1: 8 → 4 → 2  (합: 14)
경로 2: 8 → 4 → 6  (합: 18)
경로 3: 8 → 12 → 10  (합: 30)
경로 4: 8 → 12 → 14  (합: 34)

경로는 방문의 순서이다.
경로 1: ¹8 → ²4 → ⁴2
경로 2: ¹8 → ²4 → ⁵6
노드 인덱스로 경로를 표현하면 1 → 2 → 4, 1 → 2 → 5 가 된다.

1. 같은 노드를 다른 경로에서 접근할 때마다 달라지는 경우

   • 루트에서 리프까지의 모든 경로를 탐색해야 한다.

   • {8 → 4 → 2}, {8 → 4 → 6}, {8 → 12 → 10}, {8 → 12 → 14} 경로에 따라 방문한 노드의 총합이 달라진다.

2. 모든 가능한 경로를 탐색해야 하는 경우 (모든 경로 찾기)

   • 경로 자체를 모두 저장해야할 때도 있다.

   • 예를 들어, 모든 가능한 경로를 조건에 따라 필터링하는 경우

     • ex) 합이 20 이상인 경로의 갯수를 찾으시오

두 경우 모두 노드 방문 여부를 경로마다 새로 지정해야된다. 이를 위해 백트래킹을 다음과 같이 구성할 수 있다.

function treeBacktracking(graph, node, path = [], sum = 0, result = []) {
    path.push(node); // 1. 현재 노드를 경로에 추가
    sum += node; // 2. 현재 노드를 포함한 경로의 합을 계산

    /*  
    3. 재귀 함수의 중단점 (Base Case)
       - !graph[node]는 해당 노드가 리프 노드임을 의미.
       - 즉, 현재 노드가 자식을 갖고 있지 않다면 경로 탐색을 종료함.
       - 이 시점에서 현재까지의 경로(path)와 그 합(sum)을 저장.
    */
    if (!graph[node] || graph[node].length === 0) {
        result.push([path.slice(), sum]); // path를 복사하여 저장 (참조값 방지)
        // 현재 경로가 저장된 후 함수는 종료되며, 콜 스택에서 하나씩 사라짐.
        return; // 경로가 끝났으므로 더 이상 탐색하지 않고 종료
    }

    /* 
    4. 현재 노드 기준으로 모든 가능한 경로를 탐색 (DFS 재귀 호출)
       - graph[node]의 인접 노드들을 탐색하며 DFS를 수행
       - 예를 들어, 첫 실행이라면 node = 8이므로 graph[8]의 자식인 [4, 12]를 방문함.
       - 즉, 8 → 4 또는 8 → 12 중 한 경로를 따라가게 됨.
    */
    for (let neighbor of (graph[node] || [])) {
        dfsBacktracking(graph, neighbor, path, sum, result);
        /*
        - 각 재귀 호출은 새로운 "탐색 과정"을 시작함.
        - 예를 들어, 8 → 4 → 2로 이동하면 path = [8, 4, 2], sum = 14가 됨.
        - 이후 2는 리프 노드이므로 (Base Case) result에 추가된 후 백트래킹 실행됨.
        */
    }

    /* 
    5. 백트래킹 (이전 상태로 되돌아감)
       - 현재 탐색이 끝났으므로, 경로에서 현재 노드를 제거
       - 이렇게 하면 다른 경로 탐색 시 이전 경로에 영향을 주지 않음
       - 예를 들어, [8, 4, 2] 탐색 후 [8, 4, 6]을 탐색할 수 있도록 2를 제거
    */
    path.pop();
}

이 함수는 주어진 그래프가 트리 형태이고 모든 방문 경로를 탐색해야 했기 때문에 visited 변수를 사용하지 않았다. 그래프가 트리가 아니더라도 이러한 백트래킹 구현은 가능하다.

• 순환이 있는 그래프에서는 visited를 사용하여 무한 루프를 방지해야 한다.

function dfsBacktracking(graph, node, visited = new Set()) {
	if (visited.has(node)) return; // 이미 방문한 노드라면 중단 (순환 방지)
	visited.add(node); // 방문 처리

	// 현재 노드 처리
	// graph[node] , 저징 값 업데이트

	for (let neighbor of graph[node]) {
		dfsBacktracking(graph, neighbor, visited); // 재귀 호출
	}
    // 인접 노드 방문 이후에 백트래킹을 추가한다
	// 백트래킹: 방문 기록 삭제하면 다른 경로에서 다시 방문 가능하다
	visited.delete(node); 
}

3-4. 순회(Traversal)

DFS는 많은 경우 전위 순회이다. 앞서 살핀 구현체들은 기본적으로 DFS를 전위 순회로 구현한다. 전위 순회는 모든 노드를 탐색하여 데이터를 수집할 때 사용한다.

하지만 경우에 따라 중위, 후위 순회가 필요할 때도 있다. 이전 글에서 전/중/후위에 대한 내용을 다뤘으니, 구체적으로 DFS에서 중위, 후위 순회를 구현하는 방법을 알아보자.

A. 중위 순회(Inorder Traversal)

중위 순회는 "왼쪽 → 현재 노드 → 오른쪽" 순으로 방문한다. 이진 탐색 트리(BST)에서 정렬된 순서로 데이터를 얻고 싶을 때 사용한다. 하지만 드물게 주어진 그래프가 이진 탐색 트리가 아닐 때도 있다. 이런 경우 특정 기준에 따라 그래프 중심을 기준으로 왼쪽과 오른쪽을 나누어 탐색한다. (하지만 대부분 이진 탐색 트리가 주어진다.)

• 이진 탐색 트리(BST)에서 정렬된 순서로 데이터를 얻고 싶을 때

  • ex: 이진 탐색 트리의 노드를 오름차순으로 출력

• 그래프에서 특정 기준을 중심으로 왼쪽과 오른쪽을 나누어 탐색할 때

이진 탐색 트리 중위 순회하기 :
이진 탐색 트리는 특정 규칙을 만족하는 계층 구조를 이룬다. 중위 순회에서 이진 탐색 트리와 함께 K번째 숫자가 무엇인지 혹은 숫자 N의 K가 무엇인지 묻는 질문이 일반적이다.

// 탐색하려는 트리가 이진 탐색 트리로 이미 구성된 경우이다.
// K번째 원소 찾기

// 외부 변수와 재귀 함수를 사용한다.
let result = -1 // 못 찾을 시 -1 반환
let count = 0

function dfsInorderKthSmallest(tree, index, count, k) {
    if (index >= tree.length) return; // 1. 배열 범위를 벗어나면 종료

    const leftIndex = 2 * index + 1; // 2. 왼쪽 자식 인덱스 계산
    const rightIndex = 2 * index + 2; // 3. 오른쪽 자식 인덱스 계산

    // 4. 왼쪽 서브트리 탐색 (BST에서 작은 값들이 위치)
    dfsInorderKthSmallest(tree, leftIndex, count, k, result);
    
    // 5. 현재 노드 방문 (중위 순회의 핵심: 왼쪽 탐색 후 현재 노드 방문)
    // 카운트를 더한다 = 노드 깊이가 깊어진다 (재귀 함수 호출될 때마다)
    count += 1;
    if (count === k) {
    // K와 같다면 외부 변수 result에 해당 노드 값을 저장하고
        result = tree[index]; 
        return; // 탐색을 종료한다
    }

    // 6. 오른쪽 서브트리 탐색 (BST에서 큰 값들이 위치)
    dfsInorderKthSmallest(tree, rightIndex, count, k, result);
}


const bstArray = [5, 3, 8, 2, 4, 7, 10, 1, 6, 9, 12]; 
dfsInorderKthSmallest(bstArray, 0 , k);

console.log(`${k}번째 작은 원소:`, result);

그래프 중심을 설정하고 중위 순회하기

중위 순회가 필요한데 그래프가 정렬되어있지 않을 수 있다. 중위 순회의 왼쪽->현재 -> 오른쪽 순서로 방문하기 위해, 방문 중 인접 노드를 정렬할 필요가 생길 수 있다.

// 전역 변수 (결과 저장)
let result = []; // 중위 순회 방문 순서 저장
let visited = new Set(); // 방문 여부 확인

// 1차원 배열 리스트 그래프에서 중위 순회하기
function dfsInorderGraph(graph, index) {
// 1. 배열 범위를 벗어나거나 이미 방문한 노드라면 탐색 중단
    if (index >= graph.length || visited.has(index)) return; 
    
    visited.add(index); // 2. 현재 노드를 방문 처리

    // 3. 인접 노드를 특정 기준(예: 숫자 크기순)으로 정렬
    let neighbors = graph[index] ? [...graph[index]]
    // 문제에 따라 정렬 기준이 달라진다 (숫자 크기순, 문자열 정렬, 가중치 등)
    .sort((a, b) => a - b)  
    : [];
    // 그래프[인덱스]가 인접 노드(인덱스)를 배열로 갖고 있어야

    let mid = Math.floor(neighbors.length / 2);
    // `mid`를 기준으로 왼쪽과 오른쪽을 나누어 탐색할 수 있다.
    // 정렬되지 않은 그래프에서 "왼쪽/오른쪽" 개념이 없기 때문에,
    // "중앙값"으로 왼쪽/오른쪽 기준을 정한다.

    // 4. 왼쪽 부분 탐색 (중앙 값 이전, 왼쪽 서브 트리를 먼저 탐색)
    for (let i = 0; i < mid; i++) {
        dfsInorderGraph(graph, neighbors[i]);
    }

    // 5. 중위 순회 핵심 부분: 왼쪽을 탐색한 후, 현재 노드 방문
    result.push(index);
    // 현재 노드를 result에 저장하고, 오른쪽 서브 트리를 탐색한다.
    
    // 6. 오른쪽 부분 탐색 (오른쪽 서브 트리)
    for (let i = mid; i < neighbors.length; i++) {
        dfsInorderGraph(graph, neighbors[i]);
    }
}

B. 후위 순회(Postorder Traversal)

후위 순회는 "왼쪽 → 오른쪽 → 루트 (현재 노드)" 순으로 방문한다. 후위 순회는 주로 트리 구조에서 많이 사용된다. 하위 노드를 모두 처리한 후 부모 노드를 방문해야 하는 경우에 적합하다. 예를 들어, 각 노드에서 자식 노드를 먼저 계산한 후, 부모 노드에서 최종 값을 계산해야 할 때가 있다.

• 구조를 완전히 탐색한 후, 정리 과정에서 데이터를 처리할 때

• 특히 트리에서 서브트리를 모두 방문한 후 부모 노드를 처리할 때

  • ex1: 각 노드를 루트로 하는 서브트리의 크기를 구하시오.

  • ex2: 각 노드에서 가장 긴 경로를 구하시오.

  • ex3: 각 노드에서 자식 노드의 값을 모두 더한 후, 현재 노드 값을 갱신하시오.

• 트리 직렬화 및 역직렬화

  • 생각하지 못했는데 다음 상황에서도 유용하다고 한다.

  • 트리를 배열로 변환 / 배열을 트리로 변환

후위 순회로 서브 트리 크기 계산하기

function dfsPostorderSubtree(graph, node, visited = new Set(), subtreeSize = []) {
	// 1. 이미 방문한 노드는 크기 0으로 처리
    if (visited.has(node)) return 0;
    visited.add(node); // 2. 현재 노드를 방문 처리

	// 3. 현재 노드도 서브트리 크기에 포함해야 하므로 초기 크기를 1로 설정
    let size = 1; 
    // 재귀 함수로 하위 트리로 갈 때마다 1로 초기화 되고,

    for (let neighbor of (graph[node] || [])) {
    // 4. 인접 노드들 = 하위 노드의 크기를 먼저 계산 
        size += dfsPostorderSubtree(graph, neighbor, visited, subtreeSize); 
		// 이 부분에서 하위 노드 크기만큼 size에 1이 더해진다.
    }
	// 5. 모든 하위 노드 크기를 합한 후, 현재 노드에 저장 (후위 순회)
    subtreeSize[node] = size; 
    // 6. 현재 노드의 서브트리 크기를 반환
    return size; 
}

후위 순회로 모든 경로 저장하기
후위 순회와 함께 백트래킹으로 모든 경로를 저장한다.

function dfsPostorderPaths(graph, node, visited = new Set(), path = [], result = []) {
    // 1. 이미 방문한 노드라면 중단 (순환 방지)
    if (visited.has(node)) return; 
    visited.add(node); // 2. 현재 노드를 방문 처리

    path.push(node); // 3. 현재 노드를 경로에 추가
    // 재귀 호출이 끝난 후 백트래킹할 때 path에서 제거됨.
    // 재귀 함수가 호출될 때마다 새로운 노드가 path에 추가됨.

    // 4. 현재 노드가 리프 노드인 경우 (자식 노드가 없음)
    if (!graph[node] || graph[node].length === 0) {
        result.push([...path]); 
        // 경로를 저장해야 하므로 path 배열을 복사하여 추가.
        // 원본 path를 그대로 저장하면 나중에 값이 변할 수 있음.
    }

    for (let neighbor of (graph[node] || [])) {
        // 5. 모든 하위 노드를 탐색 (후위 순회)
        dfsPostorderPaths(graph, neighbor, visited, path, result);
    }

    path.pop(); // 6. 백트래킹: 현재 노드를 경로에서 제거
    // 경로가 하나 저장된 후, 이전 상태로 되돌리기 위해 마지막으로 추가된 노드를 제거

    visited.delete(node); // 7. 방문 기록 삭제 (다른 경로에서 다시 방문 가능하도록)
}

후위 순회로 그래프의 누적 값 계산하기

// values는 외부 변수이다.
function dfsPostorderSum(graph, node, visited = new Set(), nodeValues = {}) {
    // 1. 이미 방문한 노드라면 0을 반환 (순환 방지)
    if (visited.has(node)) return 0;
    visited.add(node); // 2. 현재 노드를 방문 처리

    // 3. 현재 노드의 초기 값을 설정
    let sum = nodeValues[node] || 0;
    // 노드 자체가 가지는 값을 초기값으로 설정 (없다면 기본값 0)

    for (let neighbor of (graph[node] || [])) {
        // 4. 모든 하위 노드의 값을 먼저 누적 (후위 순회)
        sum += dfsPostorderSum(graph, neighbor, visited, values, nodeValues);
        // 재귀 호출을 통해 하위 노드들의 값을 반환받고 sum에 추가
        // 예: 노드 2의 자식 노드가 4, 5이고, 각각의 값이 1, 2라면
        // sum += (4의 값 + 5의 값) 이 되어 sum이 누적됨.
    }

    // 5. 모든 자식 노드의 값을 누적한 후 현재 노드의 값을 저장
    values[node] = sum;
    // 현재 노드의 누적값을 외부 변수에 저장한다.

    return sum; // 6. 현재 노드의 누적 값을 반환
}