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

깊이 우선 탐색법(DFS)는 현재 문제에 대해 접근할 수 있는 모든 경우를 순서대로 접근하는 방식이다. (백트래킹이라고도 한다)

따라서 앞선 순서의 경우가 먼저 깊게 내려가므로 앞선 경우를 따라 끝까지 검색한다음 다시 다른 경우가 있는 이전 깊이로 돌아와서 다른 경우로 깊게 내려가게 된다.

 

트리로 나타내면 이렇다.

 

 위 의 이미지 파일처럼 1번 부터 7번 순서대로 데이터를 검색하는 것이다.

 

 

보통 DFS는 제귀함수로 구현이 가능하다.

 

한번 DFS를 사용해 보겠다 

 

예를 들어, 반0 고등학교에서는 매주 월요일 부터 금요일 까지 매일 맛있는 점심이 나온다고 한다.

하지만, 문제는 조리사가 만들 수 있는 요리는 3종류 밖에 되지 않는다는 것이다.

조리사가 만들수 있는 요리는 김치 볶음밥,  우동, 스파게티이다.

그렇다면 월요일부터 금요일까지 한주동안 반0고등학교에서 나올수 있는 점심의 급식표들을 모두 출력하는 프로그램을 DFS를 이용해 만들어 보자.

 

 

 

#include <iostream>

#include <windows.h>
#include <string>

using namespace std;

string recipe[3] = {"김치볶음밥", "우동", "스파게티"};
int week[5]; //급식표.

void menu(int day){

     int i;
    
     if(day == 5){
            for(i=0;i<5;i++)cout<<recipe[week[i]]<<"//";
            cout<<endl;
            return;
     }//5일 까지 검색하고 한줄띄고 돌아감.
    
     for(i=0 ; i<3;i++){//5가지의 레시피를 하나씩 해당 날짜의 메뉴에 넣는다.
            
             week[day]=i;
            
             menu(day+1);//다음날의 메뉴를 검색한다.                  
     }
} 

int main(){

    menu(0);
   
    system("PAUSE");
       
    return 0;
}  

다음은 결과이다. 

 

김치볶음밥//김치볶음밥//김치볶음밥//김치볶음밥//김치볶음밥//

김치볶음밥//김치볶음밥//김치볶음밥//김치볶음밥//우동//
김치볶음밥//김치볶음밥//김치볶음밥//김치볶음밥//스파게티//
김치볶음밥//김치볶음밥//김치볶음밥//우동//김치볶음밥//
김치볶음밥//김치볶음밥//김치볶음밥//우동//우동//
김치볶음밥//김치볶음밥//김치볶음밥//우동//스파게티//
김치볶음밥//김치볶음밥//김치볶음밥//스파게티//김치볶음밥//
김치볶음밥//김치볶음밥//김치볶음밥//스파게티//우동//
김치볶음밥//김치볶음밥//김치볶음밥//스파게티//스파게티//
김치볶음밥//김치볶음밥//우동//김치볶음밥//김치볶음밥//
김치볶음밥//김치볶음밥//우동//김치볶음밥//우동//
김치볶음밥//김치볶음밥//우동//김치볶음밥//스파게티//
김치볶음밥//김치볶음밥//우동//우동//김치볶음밥//
김치볶음밥//김치볶음밥//우동//우동//우동//
김치볶음밥//김치볶음밥//우동//우동//스파게티//
김치볶음밥//김치볶음밥//우동//스파게티//김치볶음밥//
김치볶음밥//김치볶음밥//우동//스파게티//우동//
김치볶음밥//김치볶음밥//우동//스파게티//스파게티//
김치볶음밥//김치볶음밥//스파게티//김치볶음밥//김치볶음밥//
김치볶음밥//김치볶음밥//스파게티//김치볶음밥//우동//
김치볶음밥//김치볶음밥//스파게티//김치볶음밥//스파게티//
김치볶음밥//김치볶음밥//스파게티//우동//김치볶음밥//
김치볶음밥//김치볶음밥//스파게티//우동//우동//
김치볶음밥//김치볶음밥//스파게티//우동//스파게티//
김치볶음밥//김치볶음밥//스파게티//스파게티//김치볶음밥//
김치볶음밥//김치볶음밥//스파게티//스파게티//우동//
김치볶음밥//김치볶음밥//스파게티//스파게티//스파게티//
김치볶음밥//우동//김치볶음밥//김치볶음밥//김치볶음밥//
김치볶음밥//우동//김치볶음밥//김치볶음밥//우동//
김치볶음밥//우동//김치볶음밥//김치볶음밥//스파게티//
김치볶음밥//우동//김치볶음밥//우동//김치볶음밥//
김치볶음밥//우동//김치볶음밥//우동//우동//
김치볶음밥//우동//김치볶음밥//우동//스파게티//
김치볶음밥//우동//김치볶음밥//스파게티//김치볶음밥//
김치볶음밥//우동//김치볶음밥//스파게티//우동//
김치볶음밥//우동//김치볶음밥//스파게티//스파게티//
김치볶음밥//우동//우동//김치볶음밥//김치볶음밥//
김치볶음밥//우동//우동//김치볶음밥//우동//
김치볶음밥//우동//우동//김치볶음밥//스파게티//
김치볶음밥//우동//우동//우동//김치볶음밥//
김치볶음밥//우동//우동//우동//우동//
김치볶음밥//우동//우동//우동//스파게티//
김치볶음밥//우동//우동//스파게티//김치볶음밥//
김치볶음밥//우동//우동//스파게티//우동//
김치볶음밥//우동//우동//스파게티//스파게티//
김치볶음밥//우동//스파게티//김치볶음밥//김치볶음밥//
김치볶음밥//우동//스파게티//김치볶음밥//우동//
김치볶음밥//우동//스파게티//김치볶음밥//스파게티//
김치볶음밥//우동//스파게티//우동//김치볶음밥//
김치볶음밥//우동//스파게티//우동//우동//
김치볶음밥//우동//스파게티//우동//스파게티//
김치볶음밥//우동//스파게티//스파게티//김치볶음밥//
김치볶음밥//우동//스파게티//스파게티//우동//
김치볶음밥//우동//스파게티//스파게티//스파게티//
김치볶음밥//스파게티//김치볶음밥//김치볶음밥//김치볶음밥//
김치볶음밥//스파게티//김치볶음밥//김치볶음밥//우동//
김치볶음밥//스파게티//김치볶음밥//김치볶음밥//스파게티//
김치볶음밥//스파게티//김치볶음밥//우동//김치볶음밥//
김치볶음밥//스파게티//김치볶음밥//우동//우동//
김치볶음밥//스파게티//김치볶음밥//우동//스파게티//
김치볶음밥//스파게티//김치볶음밥//스파게티//김치볶음밥//
김치볶음밥//스파게티//김치볶음밥//스파게티//우동//
김치볶음밥//스파게티//김치볶음밥//스파게티//스파게티//
김치볶음밥//스파게티//우동//김치볶음밥//김치볶음밥//
김치볶음밥//스파게티//우동//김치볶음밥//우동//
김치볶음밥//스파게티//우동//김치볶음밥//스파게티//
김치볶음밥//스파게티//우동//우동//김치볶음밥//
김치볶음밥//스파게티//우동//우동//우동//
김치볶음밥//스파게티//우동//우동//스파게티//
김치볶음밥//스파게티//우동//스파게티//김치볶음밥//
김치볶음밥//스파게티//우동//스파게티//우동//
김치볶음밥//스파게티//우동//스파게티//스파게티//
김치볶음밥//스파게티//스파게티//김치볶음밥//김치볶음밥//
김치볶음밥//스파게티//스파게티//김치볶음밥//우동//
김치볶음밥//스파게티//스파게티//김치볶음밥//스파게티//
김치볶음밥//스파게티//스파게티//우동//김치볶음밥//
김치볶음밥//스파게티//스파게티//우동//우동//
김치볶음밥//스파게티//스파게티//우동//스파게티//
김치볶음밥//스파게티//스파게티//스파게티//김치볶음밥//
김치볶음밥//스파게티//스파게티//스파게티//우동//
김치볶음밥//스파게티//스파게티//스파게티//스파게티//
                                 .
                                 .
                                 .

스파게티//우동//우동//스파게티//스파게티//
스파게티//우동//스파게티//김치볶음밥//김치볶음밥//
스파게티//우동//스파게티//김치볶음밥//우동//
스파게티//우동//스파게티//김치볶음밥//스파게티//
스파게티//우동//스파게티//우동//김치볶음밥//
스파게티//우동//스파게티//우동//우동//
스파게티//우동//스파게티//우동//스파게티//
스파게티//우동//스파게티//스파게티//김치볶음밥//
스파게티//우동//스파게티//스파게티//우동//
스파게티//우동//스파게티//스파게티//스파게티//
스파게티//스파게티//김치볶음밥//김치볶음밥//김치볶음밥//
스파게티//스파게티//김치볶음밥//김치볶음밥//우동//
스파게티//스파게티//김치볶음밥//김치볶음밥//스파게티//
스파게티//스파게티//김치볶음밥//우동//김치볶음밥//
스파게티//스파게티//김치볶음밥//우동//우동//
스파게티//스파게티//김치볶음밥//우동//스파게티//
스파게티//스파게티//김치볶음밥//스파게티//김치볶음밥//
스파게티//스파게티//김치볶음밥//스파게티//우동//
스파게티//스파게티//김치볶음밥//스파게티//스파게티//
스파게티//스파게티//우동//김치볶음밥//김치볶음밥//
스파게티//스파게티//우동//김치볶음밥//우동//
스파게티//스파게티//우동//김치볶음밥//스파게티//
스파게티//스파게티//우동//우동//김치볶음밥//
스파게티//스파게티//우동//우동//우동//
스파게티//스파게티//우동//우동//스파게티//
스파게티//스파게티//우동//스파게티//김치볶음밥//
스파게티//스파게티//우동//스파게티//우동//
스파게티//스파게티//우동//스파게티//스파게티//
스파게티//스파게티//스파게티//김치볶음밥//김치볶음밥//
스파게티//스파게티//스파게티//김치볶음밥//우동//
스파게티//스파게티//스파게티//김치볶음밥//스파게티//
스파게티//스파게티//스파게티//우동//김치볶음밥//
스파게티//스파게티//스파게티//우동//우동//
스파게티//스파게티//스파게티//우동//스파게티//
스파게티//스파게티//스파게티//스파게티//김치볶음밥//
스파게티//스파게티//스파게티//스파게티//우동//
스파게티//스파게티//스파게티//스파게티//스파게티//
Press any key to continue . . .

 

총 3⁵ 개 이므로 전부다 출력하기엔 너무 길어지므로 중간을 생략하였다.