Today I Learned

내일 있을 코테를 대비해 코테를 풀었다.

N과 M (9)

백준 11663 https://www.acmicpc.net/problem/15663

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

• 입력
  4 2
  9 7 9 1
• 출력
  1 7
  1 9
  7 1
  7 9
  9 1
  9 7
  9 9

문제 풀이

• 주어진 숫자 배열에서 중복되지 않는 M개의 숫자 조합을 모두 출력하는 문제로 백트래킹을 사용해 풀었다.

1. n, m을 입력으로 받아준다. 그 다음 숫자들을 입력받아 map을 이용해 정렬된 숫자 배열로 바로 담아둔다. 방문 체크용 boolean 배열과 결과를 저장할 링크드 리스트를 초기화한다.

2. 백트래킹 함수를 만든다. 숫자배열에서 숫자를 선택하고, 선택한 숫자를 제외한 배열을 재귀적으로 탐색하면서 depth를 파라미터로 넘기는 방식으로 구현한다. 중복되지 않는 조합을 구해야하니 이미 선택한 숫자는 다시 선택하지 않도록 visited에서 방문여부를 체크한다.

3. 백트래킹 함수를 dfs 방식처럼 재귀적으로 동작되면서 현재까지 선택한 숫자들을 담은 리스트를 결과로 반환한다. 현재까지 선택한 숫자의 개수가 m에 도달하면 결과 리스트에 추가하고, 아니면 가능한 모든 숫자를 탐색해 다음 숫자를 선택한다.

4. 결과리스트에는 중복되지 않은 모든 조합이 담겨있게 되는데 이를 for문으로 하나씩 출력하면 완료!

Kotlin 코드

import java.util.*

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val numbers = readln().split(" ").map { it.toInt() }.sorted().toIntArray()
    val visited = BooleanArray(n)

    val result = LinkedList<Int>()
    val answer = LinkedList<List<Int>>()

    fun backtracking(depth: Int) {
        if (depth == m) {
            answer.add(result.toList())
            return
        }

        var prev = 0
        for (i in 0 until n) {
            if (!visited[i] && prev != numbers[i]) {
                visited[i] = true
                result.add(numbers[i])
                prev = numbers[i]
                backtracking(depth + 1)
                visited[i] = false
                result.removeLast()
            }
        }
    }

    backtracking(0)

    for (list in answer) {
        println(list.joinToString(" "))
    }
}