[c++] DFS 깊이 우선 탐색 , 재귀함수

 

 

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

• 현재 지점에서 정해놓은 지점까지 노드를 깊게 탐색하는 방식
• 스택 또는 재귀함수로 구현한다.

 

 

 

 

재귀함수

• 자기 자신을 계속해서 호출한다.

1. 초기화
2. 끝나는 조건 (if문)
3. 가지(branch) / 재귀조건

 

 

 

 

Q. 재귀함수 예시문제

숫자 n을 입력 받으세요.

숫자 n부터 0까지 Count down 했다가

다시 돌아오는 수를 출력 하시면 됩니다.

ex) 4

4 3 2 1 0 1 2 3 4

ex ) 6

6 5 4 3 2 1 0 1 2 3 4 5 6

 

#include<iostream>

using namespace std;

void abc(int num)
{
	cout << num << " ";

	//종료조건
	if (num == 0)
	{
		return;
	}
	//재귀조건
	abc(num - 1);

	cout << num<< " ";
}

int main()
{
	//초기화
	int n;
	cin >> n;

	abc(n);

	return 0;
}

 

위의 재귀함수가 사용된 코드를 예시로 살펴보면,

 

1. main 함수에서 재귀함수에 초기값을 넣어준다.

보통 어느깊이까지 갈 것인지 나타내는 lev이 될 수  -> lev 

혹은

처음 출력할 대상을 넣음.   ->  a 

 

*둘 다 넣는 경우도 있다.

 

 

2. 재귀함수 안으로 들어가자.

• 처음에 num이 들어온다.
• 상단에 있는 cout 실행한다.
• '재귀조건'에 해당되는 abc(num-1)으로 가서 num이 0이 될 때까지 계속해서 abc()함수를 호출하게 된다.
• num==0이면 return즉 '돌려준다'.  
• abc(num=0)이려면 하단의 num-1의 num은 1이였어야함. 이방식으로 계속해서 되돌아간다.
• 되돌아가면서 하단의 cout을 실행한다.

 

재귀호출 위 구문: 호출 전 수행됨.
재귀호출 아래 구문: 리턴해서 돌아왔을 때 수행됨.

 

 

 

 

재귀함수와 주사위문제

Q.예시문제

주사위 3개를 돌렸을 때 모든 합을 출력하시오.

(주사위: 1~6 (111,112,113,114...666)

 

#include<iostream>

using namespace std;

void dice(int lev,int sum)
{
	if (lev == 3)  //종료조건
	{

		cout << sum;
		return;

	}

	//재귀조건
	for (int i = 1; i <= 6; i++)
	{
		//현재 레벨에서의 sum은 각자 다 다르다.
        //가지의 갯수를 for문으로 표현함.
		dice(lev + 1, sum + i);
	}
	
}

int main()
{
	dice(0, 0); 
	
	return 0;
}

• 가지의 갯수를 for 문으로 표현함.
  ex) 주사위 눈금이 6개여서 for문을 6번 돌림.
• i : 가지, 눈금