boj15649 N과 M (1)_java

링크

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

문제

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

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

나의 풀이

• dfs로 탐색하였다. checked 가 false 인 경우 true로 체크하고, cnt++ 을 해준다. 그리고, cnt가 M 이 되는 경우, StringBuilder 에 answer 배열을 내보내고, return 시킨다. 재귀에서 다시 백하면, checked 를 다시 false로 돌려주고, for문을 진행시킨다.
• 사실 dfs에 대한 개념을 알면 너무나도 쉽게 바로 풀릴 문제다.
• 이 문제가 어렵거나 잘 이해되지 않으면 dfs에 대한 개념 공부를 하면 좋을 것같다.(사실 본인도 이 문제 풀기전에 다시 공부했다...)
• 핵심 코드

  private static void dfs(int N,int M,boolean[] checked,int cnt){
      if(cnt==M){
          for (int i = 0; i < M; i++) {
              sb.append(answer[i]+" ");
          }
          sb.append("\n");
          return;
      }
  
      for (int i = 0; i < N; i++) {
          if(!checked[i]){
              answer[cnt]= i+1;
              checked[i] = true;
              dfs(N,M,checked,cnt+1);
              checked[i]= false;
          }
      }
  }

• 전체 코드

  package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.List;
  import java.util.StringTokenizer;
  
  public class boj15649 {
      static StringBuilder sb = new StringBuilder();
      static int[] answer;
      public static void main(String[] args) throws Exception{
          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());
          answer = new int[M];
          boolean[] checked = new boolean[N];
          dfs(N,M,checked,0);
  
          System.out.println(sb.toString());
      }
  
      private static void dfs(int N,int M,boolean[] checked,int cnt){
          if(cnt==M){
              for (int i = 0; i < M; i++) {
                  sb.append(answer[i]+" ");
              }
              sb.append("\n");
              return;
          }
  
          for (int i = 0; i < N; i++) {
              if(!checked[i]){
                  answer[cnt]= i+1;
                  checked[i] = true;
                  dfs(N,M,checked,cnt+1);
                  checked[i]= false;
              }
          }
      }
  }

결과