• 깊이 우선 탐색
  • 루트 노드에서 자식노드로 이동
  • 마지막 깊이에 도달한 경우 다시 상위 노드로 올라가 탐색을 재개한다

Source

  • 아래는 임의의 숫자(NUM)의 순열을 나타내는 예제이다
public class Dfs {
     final static int MAX = 7;                                  // 배열 생성을 위한 임의의 수
     final static int NUM = 3;                                  // 깊이 값
     static boolean[] visit = new boolean[MAX];       			// 방문여부  체크
     static int[] arr = new int[MAX];                           // 값 저장
     public static void dfs(final int depth){
           
           // 지정한 깊이보다 현재 깊이가 더 크면 빠져나온다
           if(NUM + 1 == depth){
                // 출력
                for(int i = 1; i <= NUM; ++i){
                      System.out.print(arr[i]+""); 
                }
                System.out.println(" ");
                
           }else{ // 탐색
                for(int i = 1; i <= NUM; ++i){
                      if(false == visit[i]){           	 // 방문하지  않았다면
                           visit[i] = true;              // 들어가지 않은 노드는 들어갔다고 표시를 한다
                           arr[depth] = i;
                           //System.out.println("depth:"+depth+"  i:"+i);
                           dfs(depth+1);            	// 한단계 깊이 들어간다
                           visit[i] = false;            // 최고 깊이에 도달해서 dfs 함수를 빠져나왔다
                           arr[depth] = 0;            	//  그래서 방문여부와 값을 초기화한다
                      }
                }
           }
     }
     
     public static void main(String[] args) {
           dfs(1);
     }
}