백준 17471번
https://www.acmicpc.net/problem/17471

문제

---

생각하기

---

• 백트래킹을 활요한 조합을 만들어서 같은 그룹인지 확인 후 기본적인 조건을 만족할 시 인구수를 파악하면 된다.

동작

    // 백트래킹
    isVisited[node] = true
    DFS(node + 1)
    isVisited[node] = false
    DFS(node + 1)

2개의 구역으로 분리하는 조합 만들기

    if (node == N) {
        val g1 = ArrayList<Int>()
        val g2 = ArrayList<Int>()

        for (i in 1..N) {
            if (isVisited[i]) {
                // 방문한 노드들은 g1에 추가
                g1.add(i)
            } else {
                // 방문되지 않은 노드들은 g2에 추가
                g2.add(i)
            }
        }

        if (g1.isEmpty() || g2.isEmpty()) return
        if (!BFS(g1) || !BFS(g2)) return

        var sum1 = 0
        var sum2 = 0
        for (num in g1) {
            sum1 += population[num]
        }

        for (num in g2) {
            sum2 += population[num]
        }

        ans = ans.coerceAtMost(abs(sum1 - sum2))
        return
    }

하나의 조합이 완성되면, 2개의 그룹으로 분리하고 BFS를 통해서 연결되어 있는지 체크한다.

모든 조건이 성공하면, 인구수를 파악해서 차이값을 구하고 최소값을 갱신해서 답을 구하면 된다.

결과

코드

---

Kotlin

import java.io.*
import java.util.*
import kotlin.math.abs

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var ans = Int.MAX_VALUE
private lateinit var population: IntArray
private lateinit var adjList: MutableList<MutableList<Int>>
private lateinit var isVisited: BooleanArray

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    DFS(1)

    if (ans == Int.MAX_VALUE) {
        sb.append(-1)
    } else {
        sb.append(ans)
    }

    return sb.toString()
} // End of solve()

private fun DFS(node: Int) {
    if (node == N) {
        val g1 = ArrayList<Int>()
        val g2 = ArrayList<Int>()

        for (i in 1..N) {
            if (isVisited[i]) {
                // 방문한 노드들은 g1에 추가
                g1.add(i)
            } else {
                // 방문되지 않은 노드들은 g2에 추가
                g2.add(i)
            }
        }

        if (g1.isEmpty() || g2.isEmpty()) return
        if (!BFS(g1) || !BFS(g2)) return

        var sum1 = 0
        var sum2 = 0
        for (num in g1) {
            sum1 += population[num]
        }

        for (num in g2) {
            sum2 += population[num]
        }

        ans = ans.coerceAtMost(abs(sum1 - sum2))
        return
    }

    // 백트래킹
    isVisited[node] = true
    DFS(node + 1)
    isVisited[node] = false
    DFS(node + 1)
} // End of DFS()

private fun BFS(group: ArrayList<Int>): Boolean {
    val que: Queue<Int> = LinkedList()
    val vis = BooleanArray(N + 1)
    que.offer(group[0])
    vis[group[0]] = true

    var cnt = 1
    while (que.isNotEmpty()) {
        val nowNode = que.poll()

        for (nextNode in adjList[nowNode]) {
            if (vis[nextNode] || isVisited[nextNode] != isVisited[nowNode]) continue

            vis[nextNode] = true
            que.offer(nextNode)
            cnt++
        }
    }

    return cnt == group.size
} // End of BFS

private fun input() {
    N = br.readLine().toInt()

    isVisited = BooleanArray(N + 1)
    population = IntArray(N + 1)
    StringTokenizer(br.readLine()).run {
        repeat(N) { idx ->
            population[idx + 1] = nextToken().toInt()
        }
    }

    adjList = ArrayList()
    repeat(N + 1) {
        adjList.add(ArrayList())
    }

    repeat(N) { idx ->
        StringTokenizer(br.readLine()).run {
            val temp = nextToken().toInt()

            repeat(temp) {
                val u = nextToken().toInt()
                adjList[idx + 1].add(u)
            }
        }
    }
} // End of input()