[종만북] 6.4 재귀호출과 완전탐색[소풍]

소풍 문제는 서로 친구들끼리 짝을 지어주는 경우의 수를 만드는 문제이다.

입력은

학생 수 와 친구 쌍의수가 주어지고

그 다음줄은 서로 친구인 두학생의 번호가 주어진다.

예를 들면

학생수는 4명 친구 쌍은 6쌍일때

0 1 1 2 2 3 3 0 0 2 1 3

 

0과 1은 친구이고, 1과 2는 친구이고.... 이렇게 숫자 2개씩 한쌍을 이룬다.

그리고 학생수는 항상 짝수이다

 

사고 과정

 

1. 문제를 잘못이해 했는데 친구가 아예 없는 경우까지 생각해서 고민을 했다.

2. 이때 생각난건 순열이었는데 중복되는 경우를 어떻게 처리할지 고민했다. 

예를 들면 (1,2) (0,3)과 (2,1) (3,0)은 같은 경우인데 순열로 나열하면 다른 경우로 들어가기 때문이다.

 

결국 순열에 집착해 옳바른 방향으로 생각하지 못하여 데이터에 대한 정의도 제대로 내리지 못했다.

친구관계를 표현하는 2차원 배열조차도 말이다.

그리고 중복을 처리하는 과정에서 배운점이 있는데

짝이 안지어진 친구중 제일 앞번호를 선택하여 짝을 지어주면 자연스레 중복이 제거된다는 점이었다.

 

중복이 반영된 소스코드

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val c = br.readLine().toInt()

    for (i in 0..c - 1) {
        val input = br.readLine().split(" ")
        val n = input[0].toInt()
        val m = input[1].toInt()
        val isFriend = Array(n) { Array(n) { false } }
        val taken = Array(n) { false }
        val str = br.readLine().split(" ")
        for (j in 0..str.size - 1 step 2) {
            isFriend[str[j].toInt()][str[j + 1].toInt()] = true
            isFriend[str[j + 1].toInt()][str[j].toInt()] = true
        }
        println(picnic(isFriend, taken))
    }
}

fun picnic(isFriend: Array<Array<Boolean>>, taken: Array<Boolean>): Int {
    var res = 0
    var isCompleted = true
    taken.forEach {
        if (it.not()) {
            isCompleted = false
        }
    }
    if (isCompleted) return 1

    for (i in 0..taken.size - 1) {
        for (j in 0..taken.size - 1) {
            if (isFriend[i][j] && taken[i].not() && taken[j].not()) {
                taken[i] = true
                taken[j] = true
                res += picnic(isFriend, taken)
                taken[i] = false
                taken[j] = false
            }
        }
    }

    return res
}

 

 

중복이 제거된 코드

 

import java.io.BufferedReader
import java.io.InputStreamReader


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val c = br.readLine().toInt()

    for (i in 0..c - 1) {
        val input = br.readLine().split(" ")
        val n = input[0].toInt()
        val isFriend = Array(n) { Array(n) { false } }
        val taken = Array(n) { false }
        val str = br.readLine().split(" ")
        for (j in 0..str.size - 1 step 2) {
            isFriend[str[j].toInt()][str[j + 1].toInt()] = true
            isFriend[str[j + 1].toInt()][str[j].toInt()] = true
        }
        println(picnic(isFriend, taken))
    }
}

fun picnic(isFriend: Array<Array<Boolean>>, taken: Array<Boolean>): Int {
    var res = 0
    var firstIndex = -1
    for (i in 0..taken.size - 1) {
        if (!taken[i]) {
            firstIndex = i
            break
        }
    }
    if (firstIndex == -1) return 1

    for (i in firstIndex + 1..taken.size - 1) {
        if (isFriend[firstIndex][i] && taken[i].not() && taken[firstIndex].not()) {
            taken[i] = true
            taken[firstIndex] = true
            res += picnic(isFriend, taken)
            taken[i] = false
            taken[firstIndex] = false
        }
    }

    return res
}

 

혹시나 위 내용이 저작권법에 위반된다면 바로 내리겠습니다.

감사합니다.