백준 15270 친구 팰린드롬 Kotlin (백트래킹)

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

15270번: 친구 팰린드롬

문제

초등학생인 재홍이는 이번 봄 학예회 때, 재홍이가 지휘를 맡고 반 친구들이 춤을 추기로 계획했다. 이 춤은 시작할 때 춤추는 친구들이 일렬로 쭉 서서 각자 막춤을 추다가, 가운데 있는 친구를 기준으로 왼쪽과 오른쪽에 있던 친구들이 두손을 마주잡고 춤을 춘다. 즉 5명의 친구가 일렬로 서있었다면, 첫 번째 친구와 다섯 번째 친구가 함께 춤을 추게 되며, 두 번째 친구와 네 번째 친구가 함께 춤을 추게 된다. 세 번째에 있던 친구는 같이 출 수 있는 친구가 없기 때문에 혼자 로봇 댄스를 춘다.

재홍이네 반 친구들은 모두 자신과 친한 친구하고만 춤을 추고 싶어한다. 재홍이는 이번 학예회에 스케일 크게 해보고 싶기 때문에 최대한 많은 친구를 무대에 세우려고 한다. 친구 관계도가 주어졌을 때, 최대 몇 명을 무대로 올려보낼 수 있는지 구해서 재홍이에게 알려주자. 친구들은 출석번호로 나타내며, 1부터 시작해서 N까지 있다. 각 친구는 오로지 하나의 출석번호를 갖는다.

A와 B가 친한 친구고, B와 C가 친한 친구라고해서 반드시 A와 C가 친한 친구는 아니다. 로봇 댄스를 추는 친구를 제외한 무대에 올라가는 친구들은 모두 각자 자신과 친한 친구하고만 춤을 춰야한다. 또한 재홍이 반 친구들은 모두 로봇 댄스를 출 수 있다.

입력

첫째 줄에 총 반친구 수 N(2<=N<=20, 재홍이 제외)와 관계도 수 M(0<=M<=(N^2-N)/2, 최대 50 제한)이 주어진다. 둘째 줄부터 M+1줄까지 친한 친구 관계는 출석번호 u, v로 나타나며 u와 v는 같지 않고, u와 v가 친한 친구라면 v와 u도 친한 친구다.

똑같은 입력은 두 번 이상 나오지 않는다. 가령 1 2 가 이미 나왔다면 1 2 또는 2 1는 입력으로 들어오지 않는다.

출력

무대에 최대한 세울 수 있는 친구의 수를 출력한다.

알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹
• 재귀

풀이

백트래킹으로 풀 수 있다.

학생이 a, b, c, d, e, f, g 로 7명이 있다고 할 때,

학생 a가 b,d,f랑 친구라면, a를 b,d,f, 각각 다 짝 지어보거나 아예 짝을 짓지 않고 다음 순서인 b를 짝 지어보며 g까지 이 과정을 반복한다.

앞에서부터 이 과정을 반복했기 때문에 g순서에선 굳이 앞에 친구들과 다시 짝을 짓지 않아도 되니, 현재 탐색하는 학생이 n번째 학생이라면 탐색을 종료한다. 만약 answer가 n보다 작다면, 남은 사람들 중에서 한 명을 로봇 댄스를 추게 하면 되므로 1을 더해준다.

예를 들면 입력이 20 0 으로 주어져서 짝을 지을 수 있는 학생이 없거나, 학생은 20명인데 짝지어진 학생들은 총 14명, 16명 등 20명이 안 되는 경우이다. 

 

코드

val br = System.`in`.bufferedReader()

var answer=0
lateinit var edge: Array<ArrayList<Int>>
lateinit var visited: BooleanArray
fun backtracking(cur: Int, cnt: Int, n: Int) {
    answer = answer.coerceAtLeast(cnt)
    if(cur >= n) return
    if (visited[cur]) {
        backtracking(cur + 1, cnt, n)
    }
    else {
        visited[cur] = true
        for (next in edge[cur]) {
            if (visited[next]) continue
            visited[next] = true
            backtracking(cur + 1, cnt + 2, n)
            visited[next] = false
        }
        visited[cur] = false
        backtracking(cur+1,cnt,n)
    }
}

fun main() = with(System.out.bufferedWriter()) {

    val (n, m) = br.readLine().split(' ').map { it.toInt() }
    edge = Array(n + 1) { ArrayList<Int>() }
    visited = BooleanArray(n + 1)
    for (i in 0 until m) {
        val (from, to) = br.readLine().split(' ').map { it.toInt() }
        edge[from].add(to)
        edge[to].add(from)
    }

    backtracking(1,0, n)
    if (answer<n) answer++
    write("$answer")

    close()
}