백준 2026 소풍 Kotlin (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/2026

2026번: 소풍

문제

원장선생님께서는 1부터 N까지 번호가 붙은 N(K ≤ N ≤ 900)명의 학생들 중에서 K(1 ≤ K ≤ 62)명의 학생들을 소풍에 보내려고 한다. 그런데 원장선생님께서는 중간에 싸움이 일어나면 안되므로 소풍을 갈 학생들이 모두 서로 친구 사이이기를 원한다. 원장선생님께서는 이러한 일을 이번에 조교로 참가한 고은이에게 친구 관계에 대한 정보를 F(1 ≤ F ≤ 5,600)개를 주시며 K명을 선발하라고 부탁하였다.

고은 조교를 도와 소풍을 가게 될 K명의 학생들을 결정하시오.

입력

첫째 줄에 공백으로 분리된 세 정수 K, N, F가 주어진다. 다음 F개의 줄에는 서로 친구 관계인 두 사람의 번호가 주어진다. 친구 관계는 상호적인 관계이므로 2번 학생이 4번 학생을 좋아하면 4번 학생도 2번 학생을 좋아한다. 같은 친구 관계가 여러 번 주어지는 경우는 없다.

출력

만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 학생의 번호가 제일 작은 것을 출력한다. 첫 번째 학생의 번호가 같은 경우라면, 두 번째 학생의 번호가 작은 경우를 출력하고, 이와 같은 식으로 출력한다.

알고리즘 분류

• 그래프 이론
• 백트래킹

풀이

백트래킹 문제이다.

주어진 입력의 크기를 보아 일반적인 조합으로 결과를 찾는 것은 시간초과임을 알 수 있다.

문제를 잘 봐야 백트래킹 조건을 찾을 수 있다.

처음엔 문제를 읽고 1,2,3,6번이 사이클이 이루어져 있으면 (k=4)명이 소풍을 갈 수 있구나 생각해서 그럼 1번부터 n번까지 k사이즈의 사이클을 찾으면 되나 싶었는데, 다시 문제를 읽어보면

그런데 원장선생님께서는 중간에 싸움이 일어나면 안되므로 소풍을 갈 학생들이 모두 서로 친구 사이이기를 원한다.

이런 조건이 있다.

모두 서로 친구 사이!

이 말은 단순 사이클을 원하는 게 아니라

1번은 2,3,6과 친해야 하고

2번은 1,3,6과 친해야 하고

3번은 1,2,6과 친해야 한다.

즉 서로 모두 연결된 간선이 있어야 한다는 것이다.

 

그렇다면 어떻게 가지치기를 할 수 있을까.

우선 1번 학생부터 n번 학생까지 검사하며 0번째 학생, 1번째 학생 ~~ k번째 학생까지 뽑아야 한다.

일반적으로 리스트를 순회할 때 앞 번호부터 한다. 이는 자연스레 사전 순으로 정답을 찾을 수 있고, 가장 먼저 나오는 정답 셋이 

아래 조건을 만족한다

여러 경우가 존재한다면 첫 번째 학생의 번호가 제일 작은 것을 출력한다. 첫 번째 학생의 번호가 같은 경우라면, 두 번째 학생의 번호가 작은 경우를 출력하고, 이와 같은 식으로 출력한다.

아무튼 0~k명의 학생을 뽑는데, 학생을 뽑는 기준은, 해당 학생이 친한 친구가 k명 이상 있어야 한다.(집합의 친구들이 모두 서로 친구여야 하므로)

즉 X학생의 간선 갯수가 k개 미만이라면 뽑을 필요가 없는 것이다. 어차피 정답이 될 수 없기 때문.

그럼 우리는 다음과 같은 식을 세울 수 있다.

if(현재 학생이 친한 학생의 수 <k){

    1.현재 학생 안 뽑고 다음 학생 검사

}

else{ //현재 학생이 친한 학생의 수가 k명 이상일 때

   1.현재 학생 뽑고 다음 학생 검사

   2.현재 학생 안 뽑고 다음 학생 검사

}

 

위 식을 재귀적으로 돌려 만약 k명의 학생을 모두 뽑았다면 이 학생들이 서로 모두 친한지 check하고 친하다면 아예 프로그램을 종료시키고, 친하지 않다면 현재 탐색은 stop, 다른 학생 결과 셋을 찾아야 한다.

위 식의 else문에서 (1.현재 학생을 뽑고 다음 학생을 검사)가 (2.현재 학생 안 뽑고 다음 학생 검사)보다 먼저 와야 재귀의 성질을 이용하여 유의미한 가지치기가 된다. 

 

위의 식으로 뽑은 k명의 학생들이 모두 서로 친한지 check는 어떻게 할까?

본인은 아래 2차원 배열로 저장했다.

isFriend[i][j] = i와 j가 친하다

이 배열을 이용해 k명의 학생을 2중 포문으로 돌리면 간단하게 확인 가능하다.

 

본인은 Edge를 쓸 일이 있을까 싶어 인접 리스트 형태로 간선을 저장해 두었는데 사실 코드에서 간선의 크기만 사용했지, 간선이 어디로 향하는지는 사용하지 않았기 때문에 인접 리스트까지는 필요 없고, 한 친구당 간선이 몇 개 존재하는지만 저장하면 된다.

isFriend라는 인접 행렬이 있기 때문이다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
val bw = System.out.bufferedWriter()
lateinit var isFriend: Array<BooleanArray>
lateinit var edge: Array<ArrayList<Int>>
var isFinish = false

fun check(result: IntArray): Boolean {
    for (i in result.indices) {
        for (j in i + 1 until result.size) {
            if (!isFriend[result[i]][result[j]]) return false
        }
    }
    return true
}

fun combination(cur: Int, idx: Int, result: IntArray, k: Int, n: Int) {
    if (isFinish) return
    if (idx == k) {
        if (check(result)) {
            isFinish = true
            for (r in result) {
                bw.write("$r\n")
            }
        }
        return
    }
    if (cur > n) return
    if (edge[cur].size + 1 < k) {
        combination(cur + 1, idx, result,k,n)
    }
    else{
        //뽑기
        result[idx] = cur
        combination(cur + 1, idx + 1, result,k,n)
        result[idx] = 0
        //안 뽑기
        combination(cur + 1, idx, result,k,n)
    }
}

fun main() {

    //input
    val (k,n,f) = getIntList()
    isFriend = Array(n + 1) { BooleanArray(n + 1) }
    edge = Array(n + 1) { ArrayList() }

    repeat (f) {
        val (from, to) = getIntList()
        isFriend[from][to] = true
        isFriend[to][from] = true
        edge[from].add(to)
        edge[to].add(from)
    }
    //solve
    combination(1, 0, IntArray(k),k,n)
    if(!isFinish) bw.write("-1")
    bw.close()
}