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 // 혹은...