[Silver III][JAVA]15649번:N과 M(2)

https://www.acmicpc.net/problem/15650
14156KM 124MB

백트래킹의 두 번째 문제

알고리즘 - 중복되는 수열을 여러 번 출력하면 안된다.

현재 arr 배열에 i가 담김과 동시에 다음 재귀에서는 i값보다 1이 큰 수부터 탐색하도록 함과 동시에 depth 또한 1 증가시키면서 재귀호출을 해주면 다음 재귀에서는 at 은 이전 재귀보다 1이 큰 상태가 되고, 반복문에서 결과적으로 이전 값보다 큰 수부터 탐색하게 된다.

그리고 이전 문제와 달리 중복방문인지를 고려할 필요가 없으므로 boolean 배열로 중복 여부를 체크할 필요 또한 없다. 차피 재귀 과정에서 만약 모든 배열에 채우지 못하는 경우에는 depth == M 이 될 수 없게되고, 반복문이 먼저 끝나기 때문에 자동으로 걸러지게 된다.

BufferedReader + StringBuilder

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

public class Main {
   public static int[] arr;
   public static boolean[] visit;
   public static StringBuilder sb = new StringBuilder();
   public static int N;

   public static int M;

   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];
       visit = new boolean[N];

       back(0, 0);
       System.out.println(sb);
   }

   public static void back(int at, int depth) {//at현재 위치
       if (depth == M) {	// 재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
           for (int val : arr) {
               sb.append(val).append(' ');
           }
           sb.append('\n');
           return;
       }
       for (int i = at; i < N; i++) {
               arr[depth] = i + 1;//현재 깊이의 위치에 i값을 담는다
               back(i + 1, depth + 1);//재귀호출
           }
       }
}