[백준] 15649번(Java)

📖 N과 M (1)

[ 문제 ]

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

💡풀이

• 현재 노드를 방문한 뒤, 그 다음 노드에 대한 탐색을 하고 return한 뒤 방문한 노드를 다시 방문 안한 것으로 처리하는 방식이다.
• 백트래킹 문제는 쉽게 말해 문을 열고 들어갔다가 다시 나올 때 문을 다시 닫아주는 방식이라고 생각하면 편하다.
• btc 메서드에 매개변수를 많이 넣었는데 이후 문제 풀이에서 이걸 전부 static 처리해서 클래스 필드 값으로 넣는 방식으로 조금 더 깔끔하게 개선했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        boolean[] vis = new boolean[N];
        ArrayList<Integer> ans = new ArrayList<>();
        btc(M, 0, vis, ans);

    }
    public static void btc(int N, int cnt, boolean[] vis, ArrayList<Integer> ans){
        if(cnt == N){
            for(int j = 0 ; j < ans.size(); j ++){
                System.out.print(ans.get(j) + " ");
            }
            System.out.println();
            return;
        }

        for(int i = 0 ; i < vis.length; i ++){
            if(!vis[i]){
                vis[i] = true;
                ans.add(i + 1);
                btc(N, cnt + 1, vis, ans);
                vis[i] = false ;
                ans.remove(ans.size() - 1);
            }
        }
    }
}

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