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

문제

---

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

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

생각하기

---

N과 M(3)보다는 오히려 쪼금더 까다로운편이었는데, 이유는 중복을 포함하지 않아야 하기 때문이었다.

동작

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

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )
    var st = StringTokenizer(br.readLine());

    N = st.nextToken().toInt()
    M = st.nextToken().toInt()
    arr = Array<Int>(M, {0});
    visit = Array<Boolean>(N+1, {false});

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

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

    for(i in 1..N) {

        if(visit[i]) continue;

        visit[i] = true;
        arr[depth] = i;
        DFS(depth + 1);
        visit[i] = false;
    }

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

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

코드

---

Kotlin

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

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

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )
    var st = StringTokenizer(br.readLine());

    N = st.nextToken().toInt()
    M = st.nextToken().toInt()
    arr = Array<Int>(M, {0});
    visit = Array<Boolean>(N+1, {false});

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

private fun DFS(depth : Int) {

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

    for(i in 1..N) {

        if(visit[i]) continue;

        visit[i] = true;
        arr[depth] = i;
        DFS(depth + 1);
        visit[i] = false;
    }

} // End of DFS