[백준 15663번] [Kotlin] N과 M (9)

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

난이도 : 실버 3
태그 : 백트래킹

 

 

설명

이번엔 새로운 변화구입니다.

5번의 문제 처럼 배열이 주어지지만,

5~8번은 n개의 자연수가 서로 다른 수 였습니다.

 

하지만 이번 문제부터는 중복될 수 있는 n개의 자연수가 주어집니다.

 

 

 

소스코드

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


lateinit var visited: Array<Boolean>
lateinit var arr: Array<Int>

var n = 0
var m = 0

val sb = StringBuilder()

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val nm = br.readLine()!!.split(" ")
    n = nm[0].toInt()
    m = nm[1].toInt()

    val st = StringTokenizer(br.readLine(), " ")

    arr = Array(n + 1) { 0 }

    for (i in 1..n) {
        arr[i] = st.nextToken().toInt()
    }
    arr = arr.sortedArray()

    visited = Array(n + 1) { false }


    dfs(1, 0, "")
    print(sb.toString())
}

fun dfs(idx: Int, len: Int, str: String) {
    if (len == m) {
        sb.append(str).append("\n")
        return
    }

    var temp = 0

    for (i in 1..n) {
        if (!visited[i] && temp != arr[i]) {
            visited[i] = true

            temp = arr[i]

            if (len == 0)
                dfs(i, 1, arr[i].toString())
            else
                dfs(i, len + 1, "$str ${arr[i]}")

            visited[i] = false
        }
    }
}

 

문자열이 중복되어 주어지며, 이전 문제처럼 풀 경우 출력 수열이 중복이 되버립니다.

1 3 3 과 같은 수열이 주어지면,

(1,3) (1,3)이 두 번 나타난다는 의미죠.

이를 막기 위해선 바로 직전의 값과 비교할 장치가 필요합니다.

 

백트래킹을 수행하기 전, 수열을 정렬하기 때문에 중복되는 수열끼리는 항상 붙어있습니다.

즉, 이전의 값과 같은지만 비교하면 됩니다.

따라서 이전의 값을 저장하는 temp 변수를 새로 만들었습니다.

매 반복마다 temp에 현재 값을 저장하고,

다음 반복회차에서 이전 회차의 temp와 현재 값을 비교하여 중복을 체크하였습니다.

 

 

후기

처음 봤을 때, 5번과 무슨 차이지? 하며 꽤 고민했던 문제였습니다.