15649

해결해야할 문제

1. 1부너 N까지(1<= M <= N <= 8) 중에 길이가 M인 수열

해결 방법

1. 백트랙킹

백트랙킹

• 어떤 노드의 유망성을 판단한 뒤 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법

브루트포스, 백트랙킹, DFS혼동 하는 경우가 있다

EX) a+b+c+d = 20 만족하는 모든 수를 구하시오(0<=a,b,c,d<=100)

• 브루트포스
  모든 경우의 수를 찾는다. a=1, b=1, c=1, d=1 부터 시작하여 a=100,b=100,c=100,d=100까지 모두 찾아보며 해당히는 값을 탐색
  장: 모든 경우를 따지니 무조건 답을 찾을 수 있다
  단: 많은 자원을 필요로한다.

• 백트랙킹
  해당 노드의 유망성을 판단한다 해당 범위 내에서 조건을 추가하여 값의 유망성을 판단, 하나라도 a=21, b=21, c=21 ,d=21일 경우 20일 가능성이 불가능하다.그러므로 a>20, b>20, c>20, d>20일 경우는 탐색하지 않는다. 필요 자원을 줄일 수 있다

• DFS(깊이우선탐색)
  트리순회의 한 형태, 하나의 순회 알고리즘으로 백트래킹에 사용되는 대표적 탐색 알고리즘 즉, 백트랙킹 방법중 하나가 DFS이다.

구현

N,M이 주어지고 중복되는 수를 제외한 모든 경우의 수를 탐색한다
재귀를 하면서 이미 방문한 노드라면 다음 노드를 탐색하도록 하기 위해 N크기의 boolean배열을 생성하고, 탐색 과정에서 값을 담을 int배열 arr을 생성

dfs함수에서 depth변수를 추가하여 depth를 통해 재귀가 깊어질 떄마다 depth를 1씩 증가시켜 M과 같아지면 더이상 재귀를 호출하지 않고 탐색과정 중 값을 담았던 arr배열을 출력하고 return 하는 역할 위해서

중복되는 수는 담을 수 없기에 방문 필요조차 없다
즉, 방문 상태를 판단하기 위해 visit[]배열이 있다,
해당 index가 방문하지 않는 노드(값)일 때만 재귀호출한다.

N과M은 자체 값이 변경되거나 할 일이 없기 때문에 전역변수로 바꾸어도 상관x
main 메소드는 static 메소드라 stsck에서도 static으로 작성

import java.util.Scanner;

public class NM15649 {
    public static int[] arr;
    public static boolean[] visit;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int M = sc.nextInt();
        int N = sc.nextInt();

        visit = new boolean[N];
        arr = new int[M];
        dfs(N,M,0);

    }
    public static void dfs(int N, int M, int depth){
        if(depth==M){
            for(int val : arr){
                System.out.println(val + " ");
            }
            System.out.println();
            return;
        }

        for(int i =0; i < N; i++){
            if(!visit[i]){
                visit[i] = true;
                arr[depth] = i + 1;
                dfs(N, M, depth + 1);
                visit[i] = false;
            }
        }
    }
}

출처: https://st-lab.tistory.com/114