[완전 탐색] N과 M(1) - 중복제외

1. 문제

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

15649번: N과 M (1)

 

2. 주의사항

• 이중 for문을 이용해서 selected배열을 모두 찾을 수도 있지만, 시간복잡도가 오래 걸리게 된다. 그래서 used라는 배열을 이용해서 선택한 숫자의 사용여부를 판단할 수 있다.
  • used : 사용한 숫자를 인덱스로 하며 사용했다면 "1" 미사용이라면 "0"을 저장한다.
  • selected : 선택한 숫자를 저장하는 배열
• 최초 호출한 재귀함수의 싸이클이 끝났을 경우 선택한 값들의 배열(selected에 저장된 값들)과 중복사용을 확인하는 배열(used)을 초기화 해줘야지 다음 싸이클에 영향을 주지 않는다.
  • ex. N=4/M=2
    • N=1 -> 진행
    • N=2 -> used 배열이 초기화 안되어 있다면 사용하지 않은 숫자이지만 전 싸이클인" N=1"의 마지막 재귀함수에서 사용한 값이 남아있어서 실제로 사용하지 않았지만 사용했다고 판단해서 오류가 발생한다. 

 

3.풀이

import java.io.*;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();

    static void input() {
        FastReader scan = new FastReader();
        N = scan.nextInt();
        M = scan.nextInt();
        selected = new int[M];
        userd = new int[N+1];
    }

    static int N, M;
    static int[] selected, userd;
    // Recurrence Function (재귀 함수)
    // 만약 M 개를 전부 고름   => 조건에 맞는 탐색을 한 가지 성공한 것!
    // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
    static void rec_func(int k) {
        if(k == M){//모두 골랐다면 출력진행
            for (int i = 0; i < M; i++) {
                sb.append(selected[i]).append(" ");
            }
            sb.append("\n");
        }else {
            for (int j = 1; j < N + 1; j++) {//j는 1 ~ N이 선택될 수 있다.
                //사용한숫자를 인덱스로 하는 배열을 사용한다.
                //사용했다면 1, 미사용이라면 0
                if(userd[j]==1) continue;
                //사용한 숫자를
                selected[k] = j;    userd[j] = 1;
                rec_func(k + 1);
                //최초 호출한 재귀호출이 끝난 후 다음 싸이클의 재귀호출 사용 시에 사용을 하지 않았지만
                // 1(사용)로 남아있으므로 0(미사용)처리(초기화)를 해줘야한다.
                selected[k] = 0;    userd[j] = 0;
            }
        }
    }

    public static void main(String[] args) {
        input();

        // 0번째 원소부터 M-1 번째 원소를 조건에 맞는 모든 방법을 찾아줘
        rec_func(0);
        System.out.println(sb.toString());

    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}