백준 2026번: 소풍 (Kotlin)

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

2026번: 소풍

안녕하세요, 이륙사입니다. 제가 요새 종만북을 보고 있는데, 알고스팟은 코틀린을 지원하지 않아서 비슷한 문제를 찾다가 발견했습니다. 결론적으로 완전히 같은 문제는 아니었지만 비슷해서 도움이 많이 됐어요!

 

풀이

이 문제는 재귀(백트래킹)를 사용하는 완전 탐색 문제였습니다.

 

단순 조합으로 생각해보면, 최대 가지수가 900C62개라서 완전 탐색으로 해결이 불가능합니다. 저도 처음엔 안될 거 같았지만, 모두 친구 사이인 경우 1가지만 찾는 것이기 때문에 백트래킹으로 완탐으로 가능할 수도 있겠다 생각했습니다. 출력도 오름차순으로 제일 작은 걸 찾으라고 해서 더 믿음을 가질 수 있었는데요, 약간의 믿음이 필요한 문제였던 것 같습니다ㅋㅋ

 

백트래킹 로직은 크게 어렵지 않았습니다.

한명씩 선택하는 과정에서 기존에 선택한 학생들과 모두 친구 사이인지 확인하고, 그렇지 않다면 바로 다음 탐색으로 넘어가는 방식으로 문제를 해결할 수 있습니다.

// 남아있는 학생들 중 첫번째 인덱스, 선택된 학생 수, 친구 관계인지?, 선택된 학생들
fun pick(start: Int, count: Int, isFriendly: Array<BooleanArray>, pickedStudents: IntArray) {
	
    ...
    
    for (i in start until isFriendly.size) {
        // 선택된 학생들과 친구라면
        if (isValid(i, count, pickedStudents, isFriendly)){
            pickedStudents[count] = i // 학생 선택
            pick(i+1, count+1, isFriendly, pickedStudents) // 재귀 호출
        }
    }

 

 

종만북의 소풍 문제와는 달리 모든 학생들과 친구 사이인지 확인해줘야 합니다!

 

생각 과정

1. 모든 조합을 확인해서 풀 수 있을까? 900C62는 너무 크다. 
2. 탐색 중간중간 가지를 쳐낸다면 가능하지 않을까? 가능한 경우 중 오름차순 하나만 찾는 거니까 더더욱 될 것 같다.
3. 믿음을 갖고 도전한다.

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.system.exitProcess


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (picnicCount, studentCount, infoCount) = readLine().split(" ").map(String::toInt)
    val isFriendly = Array<BooleanArray>(studentCount + 1) {
        BooleanArray(studentCount + 1)
    }
    val pickedStudent = IntArray(picnicCount) // 선택한 학생들을 담을 배열

    repeat(infoCount) {
        val st = StringTokenizer(readLine())
        val s1 = st.nextToken().toInt()
        val s2 = st.nextToken().toInt()

        isFriendly[s1][s2] = true
        isFriendly[s2][s1] = true
    }

    if (picnicCount == 1) { // 1명만 뽑는다면 항상 학생1을 데려갈 수 있다
        print(1)
        return
    }

    pick(0, 0, isFriendly, pickedStudent)

    print(-1)
}

// 남아있는 학생들 중 첫번째 학생, 선택된 학생 수, 친구 관계, 선택된 학생들
fun pick(start: Int, count: Int, isFriendly: Array<BooleanArray>, pickedStudents: IntArray) {
    if (count == pickedStudents.size) {
        pickedStudents.sort()
        printStudents(pickedStudents)
        exitProcess(0)
    }

    // 남아있는 학생 수 < 뽑아야할 학생 수
    if (isFriendly.size - start < pickedStudents.size - count) {
        return
    }

    for (i in start until isFriendly.size) {
        // 선택된 학생들과 친구라면
        if (isValid(i, count, pickedStudents, isFriendly)){
            pickedStudents[count] = i
            pick(i+1, count+1, isFriendly, pickedStudents)
        }

    }
}

fun printStudents(pickedStudents: IntArray) {
    val answer = StringBuilder()

    pickedStudents.forEach {
        answer.append(it).appendLine()
    }
    print(answer)
}

fun isValid(student: Int, end: Int ,pickedStudents: IntArray, isFriendly: Array<BooleanArray>): Boolean {
    for (i in 0 until end) {
        val pickedStudent = pickedStudents[i]
        if (isFriendly[student][pickedStudent].not()) {
            return false
        }
    }

    return true
}