문제
https://www.acmicpc.net/problem/1043
시행착오
처음 이 문제를 보고 어떤 방법으로 풀어보려고 하셨나요?
저는 이 문제를 보고 아래의 방법이 먼저 떠올랐습니다.
private fun getResult(): Int {
for (party in partyList) {
var update = false
for (person in party) {
if (know[person]!!) update = true
}
if (update) {
for (person in party) know[person] = true
}
}
var result = 0
for (party in partyList) {
var lie = true
for (person in party) {
if (know[person]!!) {
lie = false
break
}
}
if (lie) result++
}
return result
}
이렇게 말이죠
하지만 위의 코드는 정답이 아닙니다. 왜일까요?
10 10
1 1
2 10 1
2 9 2
2 8 3
2 7 4
2 6 5
2 5 7
2 4 8
2 3 9
2 2 10
1 1
위 예시를 통해 알아보겠습니다.
10 10
1 1
2 10 1 -> 진실을 아는 사람 1, 10
2 9 2
2 8 3
2 7 4
2 6 5
2 5 7
2 4 8
2 3 9
2 2 10 -> 진실을 아는 사람 1, 2, 10
1 1
11번째 줄에서 (2, 2, 10)이 들어왔을 때 진실을 아는 2번 참석자 때문에 9번 참석자에게 진실을 이야기해야 하는데 (4번째 줄), 실재 저의 코드에서는 진실을 아는 사람에 포함되지 않았기 때문이죠.
그래서 어떻게 풀어?
해당 문제는 union - find 알고리즘을 통해 해결할 수 있습니다.
union - find 알고리즘은 위와 달리 입력받은 순서에 따라 영향을 받지 않기 때문이죠
따라서 해당 파티에 참석한 사람들과 연결해주고
for (party in partyList) {
for (person in party) {
unionParent(party[0], person) // 해당 파티에 참석한 사람들끼리 union
}
}
연결되지 않은 사람들만 참석한 파티를 구해주면 됩니다.
var result = 0
for (party in partyList) {
var lie = true
for (person in party) {
for (knowTruth in know) {
if (findParent(person) == findParent(knowTruth)) {
lie = false
break
}
}
}
if (lie) result++
}
최종 코드
import java.util.StringTokenizer
/*
* 백준 1043번. 거짓말
* https://www.acmicpc.net/problem/1043
*/
private val know = ArrayList<Int>()
private lateinit var parent: IntArray
private lateinit var partyList: Array<ArrayList<Int>>
private fun main() {
initVariable()
val result = getResult()
printResult(result)
}
private fun initVariable() {
val br = System.`in`.bufferedReader()
val (n, m) = br.readLine().split(' ').map { it.toInt() }
parent = IntArray(size = n + 1) { it }
val st = StringTokenizer(br.readLine())
repeat(st.nextToken().toInt()) {
know.add(st.nextToken().toInt())
}
partyList = Array(size = m) { arrayListOf() }
repeat(m) { i ->
val st = StringTokenizer(br.readLine())
repeat(st.nextToken().toInt()) {
partyList[i].add(st.nextToken().toInt())
}
}
}
private fun getResult(): Int {
for (party in partyList) {
for (person in party) {
unionParent(party[0], person) // 해당 파티에 참석한 사람들끼리 union
}
}
var result = 0
for (party in partyList) {
var lie = true
for (person in party) {
for (knowTruth in know) {
if (findParent(person) == findParent(knowTruth)) {
lie = false
break
}
}
}
if (lie) result++
}
return result
}
private fun findParent(i: Int): Int {
return if (parent[i] == i) i
else findParent(parent[i])
}
private fun unionParent(i: Int, j: Int) {
val parent1 = findParent(i)
val parent2 = findParent(j)
if (parent1 < parent2) parent[parent2] = parent1
else parent[parent1] = parent2
}
private fun printResult(result: Int) {
val bw = System.out.bufferedWriter()
bw.write("$result\n")
bw.flush()
bw.close()
}