[백준] 15649번. N과 M (1)(JAVA)

문제

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

---

풀이(13분)

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

public class Main{
    static int n;
    static int m;
    static boolean[] visited;
    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());

        visited = new boolean[n+1];
        visited[0] = true;

        for(int i = 1; i < n + 1; i ++){
            dfs(i,1);
        }
    }

    public static void dfs(int num, int depth){
        if(depth == m){
            sb.append(num + " ");
            System.out.println(sb);
            sb.delete(sb.length() - 2, sb.length());
            return;
        }

        visited[num] = true;
        sb.append(num + " ");
        for(int i = 1; i < n+1; i++){
            if(!visited[i]){
                dfs(i, depth+1);
                visited[i] = false;
            }
        }
        visited[num] = false;
        sb.delete(sb.length() - 2, sb.length());
    }
}

 

dfs를 이용하여 원하는 조합의 수만큼 개수를 측정했다면 출력을하게 하는 간단한 백트레킹 문제이다.

 

중요한 부분은 StringBuilder을 이용하여 출력하기 때문에 양식을 정확히 맞추는 것.

또한, 백트레킹을 위해 적절한 부분에서 false로 재설정 해주는 것이다.