[JAVA]백준 알고리즘 15649번 : N과 M (1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

풀이

백트래킹 문제이다.

백트래킹은 브루트 포스 알고리즘과 비슷하지만, 문제를 해결하는 도중 틀렸다는 것이 확인되면 되돌아간다는 특징이 있다.

아래 코드에서 bt함수가 백트래킹을 구현한 것이다.

 

bt함수의 매개변수로 depth 변수가 있는데, 이 변수는 배열에 값을 넣을 때 사용하였고, 배열이 완성되었는지 확인하는 역할을 하였다.(완성되면 출력조건에 맞게 StringBuilder에 넣는다.)

bt함수의 for문의 진행순서는 아래와 같다.

1. i번째 수가 한 번도 사용되지 않았는지 확인한다.

2. i번째 수를 사용했다고 표시한다.

3. i번째 수를 pick배열(결과 배열)에 넣는다.

4. depth변수에 1을 더하여 bt함수를 재귀호출한다.

5. 재귀호출이 끝났으니 다시 i번째 수를 사용하지 않았다고 표시한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] pick;
    static boolean[] TF;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        pick = new int[M];
        TF = new boolean[N];

        bt(0);
        System.out.println(sb);
    }
    public static void bt(int depth) {
        if(depth == M) {
            for(int i: pick) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for(int i = 0; i < N; i++) {
            if(!TF[i]) {
                TF[i] = true;
                pick[depth] = i + 1;
                bt(depth + 1);
                TF[i] = false;
            }
        }
    }
}

 

틀린 부분이 있다면 정정해주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!