백준 [15649] , DFS(백트레킹) (Java)

 이문제에서 중복을 없애려면  그해당 값을 방문하지않고 방문처리하면됨   그리고 DFS 는 해당노드가 방문하지않은상태일때, 재귀호출 

 

DFS에대한 이해도가 예전보다 많이 올랐다.

 

 

 

 

 

 

 

 

 

 

아래는 작업한 코드전체 

/*pink.경우의수는 n X m+1 개만큼의 갯수가 나오게됨 , m  (배열의 인덱스는 0부터 시작)
* pink. val 요소를 만들어서  배열마다의 요소를 val 요소에 넣음
*/




package 백준15649;
import java.util.Scanner;
public class Main {

public static int[] arr; //red.길이가 M인 순열을 저장하기 위한 배열 arr을 선언
public static boolean[] visit; //red. 방문 여부를 위한 boolean 배열

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

    int n =  sc.nextInt();
    int m =  sc.nextInt();

    arr= new int [m];  //red. arr 배열을 길이 m으로 초기화
        //blue. 끝나는지점 : m   , 순열의 길이를나타내기때문에 m  으로 초기화
        //blue . m 은 순열의 길이 ( 가로에 출력되는길이 )
    visit = new boolean[n];//red.  visit 배열을 길이 n으로 초기화
                            //blue. ( 입력받은 n 부터 시작해야하기때문, 시작값을 0 이아닌n으로변경)
                            //blue. 숫자의범위인  n 만큼을 방문처리해야함-> 여러개의 트리중 한쪽의 트리(n)가 끝날때마다
                            //blue.    체크해야하기때문
        dfs(n,m,0); // red.    dfs 메소드로 순열을 재귀해서 구함, 초기깊이 = 0
        }
public static void dfs(int n , int m ,int depth){

if(depth==m) {              //red.  depth 가  m 에 도달하면 순열 완성
    for(int  val : arr){    // arr배열의 모든 요소를 val 에  대입하며 반복

        System.out.print(val+" "); //red. val을 공백 포함하여 출력
                                    //blue.   저장된 val 이 수열이된다.

    }
    System.out.println();
    return ;            //green.  DFS 메소드 종료
  }

for (int i = 0; i <n; i ++){ //red. 0부터 N-1까지 반복하면서 각 노드를 방문

if(!visit[i]){ //red.: i번째 노드를 방문하지 않았다면 실행
    visit[i] = true;        //blue. i번째 노드를 방문했다고 변경 ,중복 방지
    arr[depth] = i+1;       // depth 위치에 i+1 값 저장
    dfs(n,m,depth+1);  // red. 다음 깊이로 재귀호출
    visit[i]= false;        //green.  모든 자식노드 방문이 끝나고 돌아오면   초기시작점이었던 i 번째 노드를
                            //  방문하지않은상태로 다시 변경
            }
        }
    }
}