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

DFS란 다음 분기로 넘어가기전에 해당 분기를 모두 탐색하는 탐색 방법입니다.

즉 임의의 노드에서 갈수있는 만큼 깊게 들어간 후 더 이상 진행할 수 없으면 그전으로 다시 돌아가 탐색을 시작합니다.

 

1을 시작으로 DFS 탐색을 한다면 1-2-3-6-7-4-5 이런 식으로 탐색이 진행됩니다. (인접해있는 노드 중 작은 노드부터 탐색한다고 가정했을 때) 물론 정확한 탐색순서는 저장되어있는 노드 순서에 따라 다르지만, 중요한 것은 하나의 노드로부터 가장 깊게까지 탐색을 하고 막히게 되면 그전으로 돌아가 다시 탐색을 진행한다는 것입니다.

 

 

 

BFS는 큐를 사용하지만 DFS는 스택을 사용하여 쉽게 구현할 수 있습니다. 

하지만 굳이 스택 STL을 이용하지 않고 재귀함수를 이용하면 편합니다.

(재귀함수 자체가 스택처럼 저장하기 때문에)<컴퓨터는 구조적으로 스택의 원리를 사용합니다>

 

<전체 코드>

C++

#include<iostream>
#include<vector>

using namespace std;

vector<int> a[10];
bool check[10];

void dfs(int node)
{
	if (check[node])return;   //방문한 적이 있으면 되돌아가기
	check[node] = true;       //방문 표시
	printf("%d ", node);
	for (int i = 0; i < a[node].size(); i++)
	{
		int next = a[node][i];
		dfs(next);
	}
}

int main()
{
	a[1].push_back(2); //노드 1에서 노드 2로 연결
	a[1].push_back(3);
	a[2].push_back(1);
	a[2].push_back(3);
	a[2].push_back(4);
	a[2].push_back(5);
	a[3].push_back(1);
	a[3].push_back(2);
	a[3].push_back(6);
	a[3].push_back(7);
	a[4].push_back(2);
	a[4].push_back(5);
	a[5].push_back(2);
	a[5].push_back(4);
	a[6].push_back(3);
	a[6].push_back(7);
	a[7].push_back(3);
	a[7].push_back(6);
	
	dfs(1);

	return 0;
}

 

 

코틀린

import java.util.*

var a = Array(10, { mutableListOf<Int>() })
var check = BooleanArray(10,{false})

fun dfs(node: Int){

    check[node]=true
    print("$node ")
    for(i in 0..a[node].size-1){
        var next = a[node][i]
        if(check[next])continue
        dfs(next)
    }
}

fun main() {

    a[1].add(2)
    a[1].add(3)
    a[2].add(1)
    a[2].add(3)
    a[2].add(4)
    a[2].add(5)
    a[3].add(1)
    a[3].add(2)
    a[3].add(6)
    a[3].add(7)
    a[4].add(2)
    a[4].add(5)
    a[5].add(2)
    a[5].add(4)
    a[6].add(3)
    a[6].add(7)
    a[7].add(3)
    a[7].add(6)
    dfs(1)
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.