백준 15651번
https://www.acmicpc.net/problem/15651

문제

---

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

생각하기

---

DFS를 사용해서 백트래킹 탐색을 다루는 문제였다.

동작

private var N = 0;
private var M = 0;
private lateinit var arr : Array<Int>;
private val sb = StringBuilder();

    N = Integer.parseInt(st.nextToken()); // 1 ~ N
    M = Integer.parseInt(st.nextToken()); // 자리수
    
    arr = Array<Int>(M, {0});

    DFS(0);

1부터 N까시 수를 M자리수의 수열로 만드는 모든 조합을 탐색하면 된다.
중복도 포함할 수 있는 문제였다.

	// 재귀 탈출조건
	if(M == depth) {
          arr.forEach {
              sb.append(it).append(' ')
          }
          sb.append('\n');
          return;
      }

      for(i in 1..N) {
          arr[depth] = i;
          DFS(depth + 1);
      }

재귀 탈출조건은 재귀의 깊이변수 depth를 M과 같아질 경우, 자리수에 맞는 수열을 완성시켰다는 판단으로 종료를 시킨다.

결과는 StringBuilder를 통해서 수열의 값을 연결시켜서 결과를 출력했다.

코드

---

Kotlin

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

private var N = 0;
private var M = 0;
private lateinit var arr : Array<Int>;
private val sb = StringBuilder();

fun main() {
    var br = BufferedReader( InputStreamReader(System.`in`) )
    var st = StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken()); // 1 ~ N
    M = Integer.parseInt(st.nextToken()); // 자리수

    arr = Array<Int>(M, {0});

    DFS(0);
    println(sb);
} // End of main

private fun DFS(depth : Int) {

    if(M == depth) {
        arr.forEach {
            sb.append(it).append(' ')
        }
        sb.append('\n');
        return;
    }

    for(i in 1..N) {
        arr[depth] = i;
        DFS(depth + 1);
    }

} // End of DFS