백준 - N과 M (2)

public class Main {
    static int N;
    static int M;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        dfs(1,0, "");
    }

    static void dfs(int depth,int count, String str) {
        if (count == M) {
            System.out.println(str.trim());
            return;
        }

        for (int i = depth; i <= N; i++) {
            dfs(i + 1, count+1,str + " " + i);
        }
    }
}

😎매우 간단한 백트랙킹 문제입니다.
백트랙킹은 탐색을 하다가 조건에 맞지 않는다면 다음 단계로 진행하지 않는 방식을 의미합니다.

1. if 문에서 M개를 선택했다면 종료하고 아니라면 다음 단계를 진행할 수 있게 해주었습니다.

2. 메소드의 파라미터를 보면 depth,count,str이 있습니다.

• depth는 다음 번 시작위치를 의미하는데 이 값이 없다면 오름차순으로 값을 선택하기 어렵기에 위 파라미터를 설정해주었습니다.
• count는 M개가 선택되었는지를 파악하기 위한 파라미터입니다.
• str은 정답 값을 저장하기 위한 파라미터입니다.

🤓위 풀이를 응용한다면 순열, 조합, 중복 조합등 다양한 문제들을 풀 수 있습니다.

출처: 백준 - n과m(2)