TLDR

• 탐색은 방문 순서, 조회 시점, 백트래킹과 순회 방식을 최적화한다.

• 이에 따라 목적에 맞는 그래프와 탐색 알고리즘을 구성한다.

Prologue

이전 글에서 그래프의 기본 구성 요소들과 JS에서의 표현법을 알아봤다. 이전 글이 그래프 구조와 표현에 대한 글이라면, 이번에는 그래프 탐색 자체에 집중한다. 탐색을 이해하기 위한 몇가지 필수적인 개념에 집중했다.

이 글의 배경에는 DFS가 있었다. 책으로 원리를 익히고, 답을 완전히 외울 때까지 코드를 외웠는데도 도무지 응용이 되질 않았다. 새로운 유형을 만날 때마다 적절한 데이터나 탐색 함수의 구조를 떠올리기 힘들었다. 그런 노하우를 귀납적으로 얻을 수 없겠다는 생각이 들어, 반대로 기본 개념에 집중하는 연역적인 탐구를 해보았다.

그래프 탐색

그래프 탐색은 노드와 엣지를 따라가면서 그래프에서 원하는 데이터를 찾거나, 특정 경로로 탐색하는 과정이다.

• 주어진 그래프 형태에 따라 적합한 탐색법이 다르다.

• 그래프가 없는 경우, 탐색 목적에 적합한 그래프를 만든다.

여러 탐색 방법이 있지만, 가장 먼저 탐색의 기본 요소와 원리를 알아본다.

1. 방문과 조회

2. 백트래킹

3. 순회

탐색의 기본 요소들은 아래 수 많은 탐색 알고리즘에서 모두 사용된다.

graph LR
    A[그래프 탐색]
    A --> B[최단 경로 알고리즘]
    B --> B1[다익스트라 알고리즘]
    B --> B2[벨만-포드 알고리즘]
    B --> B3[플로이드-워셜 알고리즘]
    B --> B4[A* 탐색 알고리즘]
    
    A --> C[최소 신장 트리 알고리즘]
    C --> C1[프림 알고리즘]
    C --> C2[크루스칼 알고리즘]
    
    A --> D[위상 정렬]
    
    A --> E[흐름 네트워크 알고리즘]
    E --> E1[네트워크 플로우]
    E --> E2[이분 매칭]
    
    A --> F[강한 연결 요소]
    F --> F1["SCC (강한 연결 요소 분해)"]
    
    A --> G[문자열 탐색 알고리즘]
    G --> G1[KMP 알고리즘]
    G --> G2[보이어-무어 알고리즘]
    G --> G3[라빈-카프 알고리즘]

방문과 조회

탐색에서 잘 이해되지 않는 부분이 있어 그림과 이야기로 풀어보았다.

              🚪 
		   ↙      ↘          
	 	  🚪       🚪              
	    ↙  ↘     ↙   ↘          
	   🚪   🚪   🚪     🚪   
    ↙    ↘        ↘      ↘   
   🚪     🚪        🚪      🚪               
 ↙  ↘    ↙  ↘     ↙  ↘    ↙   ↘                
🚪   🚪  🚪   🚪  🚪    🚪 🚪    🚪 		  
                                            ?
                                          O
                                 		 /|\
									     / \ 

눈을 떠보니 흰 벽에 수 많은 문이 늘어서 있다.
손에 잡히는 문고리를 조심히 당겨보니, 빈 방에 작은 카펫과 문이 보인다.
카펫에 번호가 쓰여 있다. 11. 발로 슬쩍 밀어본다. 그 아래엔 열쇠가 있다.
한참을 걸려 모든 방을 둘러 본다. 모든 방은 문으로 연결되어 있다.
카펫 번호는 방마다 다르며, 열쇠는 카펫 아래에 있거나 없었다.

이 이야기에서 파악한 그래프 탐색은

• 그래프: 방으로 연결된 이 건물 자체

• 엣지: 문

• 노드: 방

• 노드 데이터: 열쇠

• 노드 인덱스: 카펫에 적힌 번호

• 조회: 카펫 아래에 열쇠가 있는 지 확인하기. 즉 노드에 저장된 값을 확인하기.

• 방문: 문을 열고 방으로 들어가기.

방문

그래프 탐색에서 방문과 조회는 분리된다. 탐색에서 현재 방문한 노드에 저장된 데이터를 확인하지 않고 다음 노드로 먼저 이동할 수 있다. 즉 방문은 다음 노드로 이동하는 과정이며, 반드시 데이터(노드 값)를 확인하지는 않는다.

탐색을 시작한다! 어떤 노드부터 방문할까?
    🚪 
   /  \ 
 🚪    🚪  

이야기에서 나는 모든 방을 살펴본다. 이를 통해 모든 방(노드)이 연결된 구조임을 알게 된다. 이처럼 방문은 탐색 노드를 이동하면서 그래프의 구조를 파악한다.

이미 방문한 곳을 알 방법이 없다면, 같은 곳을 계속 방문하여 헤맸을 것이다. 그래프 탐색에서도 노드 방문 여부를 기록할 필요가 있다.

1. 중복 방문을 방지하기 위해 방문 여부를 기록해야 한다.

2. 일반적으로 배열(리스트)이나 해시셋(set) 등을 활용하여 방문 여부를 체크한다.

3. 방문 여부를 체크하지 않으면 무한 루프에 빠질 위험이 있다.

탐색 방식에 따라 방문이 달라진다. 예를 들어, 이야기에서 '나'는 새로운 방에 들어갈 때마다 매번 카펫을 확인하기 귀찮았다. 모든 방마다 열쇠를 확인하는 대신, 다음의 규칙을 떠올렸다.

"방에 문이 두 개 있다면 항상 왼쪽 문으로 간다. 더이상 새로운 문이 나오지 않을 때까지 왼쪽 방으로 넘어간다".

이런 규칙이 탐색 알고리즘이 된다.

조회

탐색에서 방문과 조회는 구분된다. 방문이 새로운 방(노드)으로 이동하는 과정이라면, 조회는 그 방 안에서 특정 정보를 확인하는 과정이다. 즉, 방문은 이동이고 조회는 데이터를 탐색하는 행위라고 할 수 있다.

┌------┐  
|  11  |  (카펫)  
└------┘
새로운 방으로 들어왔다. 방 안에는 카펫이 있고, 그 아래에 무엇인가 있을지도 모른다.
카펫을 들추어 확인해본다. 열쇠가 있을까?
┌------┐  
|  11 /   
└----┘ 🔑
있다! 새로운 열쇠를 얻었다.

조회를 통해 데이터(열쇠)를 얻는다. 그래프 탐색의 목적은 단순히 노드를 방문하는 것만은 아니다.

1. 확인: 조회를 통해 특정 노드에 저장된 값(데이터)을 확인

2. 조건: 노드를 조회하여 데이터가 조건을 만족하지 확인

3. 결과 반환: 조회한 데이터를 바탕으로 탐색을 계속 진행할지, 멈출지를 결정

탐색 목적은 얻어야 할 데이터가 무엇이냐에 따라 나뉜다. 문과 열쇠 이야기에선 같은 문제가 주어질 수 있다.

• 모든 방에 카펫 아래 열쇠 여부를 나타내시오.

• 서로 연결된 방 중, 가장 많이 연결된 열쇠가 있는 방의 개수를 찾으시오.

• 파란색 열쇠를 찾으시오.

• 파란색 열쇠를 찾을 최단 경로를 찾으시오.

• 열쇠 5개를 찾을 수 있는 최단 경로를 찾으시오.

• 가장 적은 이동 횟수로 모든 방을 방문하는 경로를 찾으시오.

• x번 방과 y번 방으로 갈 수 있는 z번 방을 찾으시오.

이 문제들은 모두 목적, 즉 탐색으로 얻어야 할 데이터가 다르고, 탐색 방법도 달라진다. 단 하나의 노드를 조회하여 바로 목적을 달성할 수 있지만(어딘 가에 있을 파란색 열쇠 찾기), 모든 노드를 확인하거나 경로를 찾는 등, 더 복잡해질 수 있다.

백트래킹

다음 방으로 이동하다 보니, 막다른 벽을 만났다.
다시 이전으로 되돌아가서 아직 안가본 방으로 나아간다.

             ¹🚪 -- 여기부터 방문 시작했고
		   ↙      ↘          
	 	 ²🚪       🚪              
	    ↙   ↘     ↙   ↘          
	  ³🚪   🚪   🚪     🚪   
       └ 여기서 막다른 벽을 만났다. 

백트래킹은 이전으로 되돌아가 새로운 경로를 탐색한다. 막다른 길을 만나거나, 같은 방식으로 이동해도 더 이상 필요한 것을 얻을 수 없을 때 사용된다.

• 막다른 길: 더이상 탐색할 다음 노드가 없을 때

• 필요한 것 : 다음 노드를 계속 방문하더라도 탐색 목적인 데이터를 얻을 수 없을 때.

백트래킹은 탐색을 되돌리는 기법이다. 탐색 과정에서 길을 선택해 나아가지만, 때때로 잘못된 길임을 알게 된다. 이러한 경우, 다시 이전 단계로 되돌아가는 과정이 필요하다.

1. 경로 탐색: 현재 노드에서 선택한 경로가 유효하지 않다면 즉시 되돌아간다.

2. 가지 치기(Pruning): 불필요한 탐색을 줄이기 위해 조건을 검사하여 탐색을 중단한다.

3. 반복 탐색 방지: 같은 노드를 여러 번 방문하지 않도록 기록을 남긴다.

백트래킹은 탐색 알고리즘에서 결정된다. 탐색 알고리즘의 순회 방식에 따라 백트래킹은 자연스럽게 동작한다. 하지만 특정 조건을 추가하여 백트래킹을 의도적으로 일어나게 할 수도 있다.

1. 탐색 알고리즘 자체가 백트래킹을 포함하는 예시:

   • DFS : 현재 위치에서 더 이상 탐색할 노드가 없을 때 이전 단계로 돌아간다.

   • BFS : 같은 레벨의 노드를 순차적으로 탐색하다가 특정 경로가 막히면 다른 층위의 노드를 선택하는 백트래킹이 일어난다.

2. 조건을 추가하여 탐색을 조정:

   • 이외의 조건을 추가해 탐색 효율을 높일 수 있다

   • 예: 목표한 노드 데이터를 찾았을 때, 특정 엣지는 탐색 제외 등

순회하기

순회는 모든 노드를 방문하는 순서를 나타낸다. 순회 방식마다 탐색 결과가 달라질 수 있다.
가장 기본적인 순회 방식은 다음 3가지다.

• 전위 순회 (Preorder)

• 중위 순회 (Inorder)

• 후위 순회 (Postorder)

이 3가지 방법 모두 그래프의 모든 노드를 방문한다. 하지만 탐색 목적에 따라 적합한 순회 방식이 다르다.

    A      -- 루트 노드
   / \
  B   C    -- B~C 리프 노드

// 높이가 3인 이진트리
           A         -- 루트 노드
         /   \
        B     C      -- B~C 서브 트리 루트 노드 
      /  \   /  \
     D    E  F   G   -- D~G 리프 노드

전위 순회

     A
   ↙ 
  B  →  C

루트 → 왼쪽 → 오른쪽 반시계 방향으로 순회한다.

전위 순회에선 부모 노드를 먼저 방문한다. 1 부모 노드를 방문한 후 2 왼쪽 서브트리와 3 오른쪽 서브트리를 순차적으로 탐색한다.

        A
      ↙   
     B  -   C
   ↙       ↙  
  D →  E  F →  G

전위 순회는 A → B → D → E → C → F → G 로 이루어진다.

A → B → D를 방문한 후 D의 자식 노드가 없기 때문에 B로 돌아가고, 이어서 E를 방문한다. 
E 또한 자식이 없으므로 다시 B로 돌아간 후, 이제 C를 방문한다. 
C에서도 같은 과정이 반복되어, C → F → G 순으로 탐색이 진행된다.

방문
전위 순회는 탐색의 초기 결정이 빠르게 이루어지는 장점이 있다. 전위 순회는 루트 노드를 가장 먼저 방문하기 때문에, 특정한 조건을 만족하는 노드를 찾을 때 탐색을 조기에 종료할 수 있다. (ex: 탐색 중 목표값 발견하면 탐색 종료)

조회
방문 순서는 당연히 조회 방식에 영향을 미친다. 전위 순회는 부모 노드를 먼저 조회하니, 자식 노드를 확인하기 전에 상위 노드에서 필요한 사전 연산을 수행할 수 있다.

백트래킹
전위 순회에서는 노드를 방문한 후 왼쪽 서브 트리부터 탐색하지만, 더 이상 방문할 노드가 없으면 되돌아가 오른쪽 서브트리를 탐색한다. 즉 백트래킹은 탐색이 막히는 순간 이전 노드로 돌아가면서 자연스럽게 발생한다. DFS(깊이 우선 탐색)는 이런 원리로 동작한다.

중위 순회

     A
   ↗   ↘ 
  B     C

왼쪽 → 루트 → 오른쪽 시계 방향으로 순회한다.

중위 순회는 1 왼쪽 서브트리를 먼저 방문한 후 2 부모 노드를 방문하고, 3 마지막으로 오른쪽 서브트리를 탐색한다.

         A
      ↗     ↘
     B        C
   ↗  ↘      ↗  ↘
  D     E   F    G

중위 순회는 D → B → E → A → F → C → G 로 이루어진다.

중위 순회는 이진 탐색 트리에서 유용하다.

이진 탐색 트리 (Binary Search Tree)

모든 왼쪽 노드는 오른쪽보다 작다.
      4
     / \
    2   6 - 왼쪽 < 오른쪽
   / \ / \
  1  3 5  7 - 왼쪽 < 오른쪽

이진 탐색 트리는 다음 조건을 모두 만족하는 이진 트리이다.

• 왼쪽 서브트리의 모든 노드 값이 루트 노드보다 x다.

• 오른쪽 서브트리의 모든 노드 값이 루트 노드보다 y다.

• 이 속성이 모든 서브트리에서 재귀적으로 유지된다.

방문
왼쪽 서브트리를 모두 방문한 후 루트 노드를 거쳐 오른쪽 서브트리를 방문하므로, 이 순서대로 탐색하면 자동으로 탐색 결과는 오름차순 정렬된 값의 리스트가 된다.

조회
이진 탐색 트리는 중위 순회로 조회하는 것이 유리하다.

      8
     / \
    4   12
   / \   / \
  2   6 10 14
 / \ / \ / \ / \
1  3 5 7 9 11 13 15

이진 탐색 트리와 중위 순회의 조합은 다음과 같은 경우에 활용된다:

• K번째 원소 찾기

  • 노드를 오름차순으로 방문하게 되므로, K번째 방문하는 노드가 K번째 작은 원소가 된다.

  • 예: K=3일 때, 중위 순회 결과가 [1, 2, 3, 4, 5, 6, 7]이라면, 3이 정답.

• 조건 범위 찾기

  • 특정 범위 [L, R]을 만족하는 노드만 선택하여 탐색을 진행할 수 있다.

  • 예: [4, 10] 범위의 노드를 찾으려면, 중위 순회를 수행하면서 해당 범위에 포함된 값만 저장.

• 범위 합산하기

  • 범위 내의 노드 값을 누적하여 합산할 수 있다.

  • 예: [3, 7] 범위의 합을 구하려면, 중위 순회를 수행하면서 3, 4, 5, 6, 7 값을 누적하여 합을 계산한다.

백트래킹
중위 순회에서는 왼쪽 서브트리를 모두 방문한 후 루트로 돌아가며 백트래킹이 발생한다. 즉, 왼쪽 끝까지 내려갔다가 하나씩 상위 노드로 되돌아오면서 오른쪽 서브트리를 탐색하는 구조다. 이러한 방식은 재귀적인 탐색과 잘 맞아떨어진다.

후위 순회

     A
       ↖ 
  B  →  C

왼쪽 → 오른쪽 → 루트 반시계 방향으로 순회한다.

후위 순회는 하위 노드를 먼저 탐색한 후 부모 노드를 방문한다. 후위 순회는 1 왼쪽 서브트리를 먼저 방문한 후 2 오른쪽 서브트리를 방문하고, 3 마지막으로 부모 노드를 방문한다.

        A  
          ↖ 
     B  -   C      
       ↖       ↖
  D  →  E  F  →  G

후위 순회는 D → E → B → F → G → C → A 로 이루어진다.

방문
왼쪽, 오른쪽 서브트리를 모두 방문한 후 부모 노드를 방문한다. 전위 순회와 정반대다. 자식 노드를 먼저 처리한 후 부모 노드에서 이를 활용하는 패턴이다.

조회
조회도 마찬가지로 1 모든 자식 2 부모 순서로 이루어진다. 따라서 하위 노드에서 출발하여 상위 노드에서 데이터를 다뤄야 하는 문제에 적합하다. 후위 순회를 활용 예시는

• 두 노드의 최초 연결 노드 찾기 (= 최소 공통 조상 LCA)

• 하위 노드의 정보를 바탕으로 상위 노드를 결정하는 그래프에서 탐색

     토너먼트 총점
        / \ 
  경기 총점   경기 총점
   / \     / \
전반전 후반전 전반전 후반전  
 / \ / \    / \  / \
1  3 5 7   9 11 13 15 
// 리프 노드 왼쪽은 A, 오른쪽은 B가 각 세트에서 낸 점수

백트래킹
후위 순회에서는 왼쪽과 오른쪽 서브트리를 모두 탐색한 후 부모 노드로 되돌아간다. 즉, 탐색 과정에서 가장 깊은 노드까지 내려간 후 되돌아오며 연산을 수행하는 방식이다.

주요 탐색법

순회 개념을 주요 탐색 방법에 적용해 본다. 탐색법의 구현과 깊은 원리는 다음 글에서 깊게 다루기로 한다. 이번엔 방문, 조회, 순회를 중심으로 알아본다.

graph TD
    A --- B
    A --- C
    B --- D
    B --- E
    C --- F
    C --- G

DFS (Depth-First Search)

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

방문

• 기본적으로 루트부터 시작하여 왼쪽 리프까지 방문한다.

• 리프에 도착하면, 백트래킹한다.

• 다시 방문하지 않은 리프를 확인한다.

• 이 과정을 반복하여 노드 전체를 방문한다.

조회

• 노드 데이터를 확인하는 단계.

• DFS를 어떻게 구현하느냐에 따라 조회 타이밍이 달라질 수 있다.

순회

• 기본적으로 전위 순회를 따른다.

• DFS 함수를 구현 방법에 따라 전위 순회를 하지 않을 수 있다.

BFS(Breadth-First Search)

BFS는 대신 "레벨" 순회를 한다. 레벨 순회는 현재 방문 위치에서 가까운 레벨(층위)부터 탐색하는 방식이다.
그래프에서 최단 경로를 찾거나 계층별 탐색을 수행할 때 사용된다. 이를 구현하기 위해 큐(Queue)를 사용하여 방문 할 노드를 순차적으로 처리한다.

graph TD
    subgraph Level 1
        A
    end

    subgraph Level 2
        B
        C
    end

    subgraph Level 3
        D
        E
        F
        G
    end

    A -->|1| B
    A -->|2| C
    B -->|3| D
    B -->|4| E
    C -->|5| F
    C -->|6| G

방문

• 루트부터 시작하여 가까운 노드(레벨 순서대로)를 먼저 방문한다.

• 큐에서 노드를 꺼내고(shift), 해당 노드의 자식 노드를 큐에 추가push한다.

• 이 과정을 반복하여 노드 전체를 방문한다.

조회

• 노드 데이터를 확인하는 단계.

• BFS는 레벨별 탐색이므로, 특정 레벨에서 데이터를 처리할 때 유용하다.

순회

• BFS는 깊이보다는 너비를 우선하여 탐색하는 방식으로 큐를 사용한다.

• 따라서 노드 방문 순서는 최단 경로를 찾거나, 계층 구조를 분석하는 문제에서 유용하다.