백준 15651번
https://www.acmicpc.net/problem/15651
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
DFS를 사용해서 백트래킹 탐색을 다루는 문제였다.
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[M];
DFS(0);
System.out.println(sb);
1부터 N
까시 수를 M
자리수의 수열로 만드는 모든 조합을 탐색하면 된다.
중복도 포함할 수 있는 문제였다.
// 재귀 탈출조건
if(depth == M) {
for(int i=0; i<M; i++) {
sb.append(arr[i]).append(' ');
}
sb.append('\n');
return;
}
for(int i=1; i<=N; i++) {
arr[depth] = i;
DFS(depth + 1);
}
재귀 탈출조건은 재귀의 깊이변수 depth
를 M
과 같아질 경우, 자리수에 맞는 수열을 완성시켰다는 판단으로 종료를 시킨다.
결과는 StringBuilder를 통해서 수열의 값을 연결시켜서 결과를 출력했다.
import java.util.*; import java.io.*; public class Main { static int arr[]; static int M, N; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { 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]; DFS(0); System.out.println(sb); } // End of main private static void DFS(int depth) { // 재귀 탈출조건 if(depth == M) { for(int i=0; i<M; i++) { sb.append(arr[i]).append(' '); } sb.append('\n'); return; } for(int i=1; i<=N; i++) { arr[depth] = i; DFS(depth + 1); } } // End of DFS } // End of Main class