[백준 15649] N과 M (1) 자바(Java) 풀이

문제 링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

[ 문제 ]

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

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

 

[ 입력 ]

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

 

[ 출력 ]

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

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

 

[ 예제 입력 1 ] 

3 1

[ 예제 출력 1 ] 

1
2
3

 

[ 예제 입력 2 ] 

4 2

[ 예제 출력 2 ] 

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

[ 예제 입력 3 ] 

4 4

[ 예제 출력 3 ] 

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

 

[ 풀이 ] 

백 트래킹 방법으로 풀이하였습니다.

문제를 풀때 주의하셔야 할 점은 depth+1과 depth++을 구별하셔야 할 거 같습니다.

depth+1은 임시적인 값이지만 depth++은 그냥 depth 값이 영구적으로 1이 증가하는 이유 때문입니다.

처음에 풀때 depth++로 풀이하여서 왜 틀렸는지 찾느라 구현하는데 오래 걸렸습니다 ㅠㅠ

StringBuilder를 사용하면 조금 더 시간이 단축될거 같습니다!

 

[ 결과 ] 

 

[ 정답 코드 ] 

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

public class Main {
   static int N;
   static int M;
   static int[] arr;
   static boolean[] check;

   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());

      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      arr = new int[M+1];
      check = new boolean[N+1];

      dfs(0);

   }

   public static void dfs(int depth) {
      if (depth == M) {
         for (int i = 0; i < M; i++) {
            System.out.print(arr[i] + " ");
         }
         System.out.println();
         return;
      }

      for (int i = 0; i < N; i++) {
         if (!check[i]) {
            check[i] = true;
            arr[depth] = i + 1;
            dfs(depth + 1);
            check[i] = false;
         }
      }

   }
}