[백준] 1043번 거짓말 (Kotlin)

SeungHyeon·2023년 1월 28일
0

BaekJoon

목록 보기
2/5
post-thumbnail

문제

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

시행착오

처음 이 문제를 보고 어떤 방법으로 풀어보려고 하셨나요?

저는 이 문제를 보고 아래의 방법이 먼저 떠올랐습니다.

  1. 진실을 아는 사람을 배열에 저장해두고
  2. 그 사람이 파티에 참석했다면 해당 파티에 참석한 사람들을 진실을 아는 사람 배열에 업데이트해 준다.
  3. 파티에 진실을 아는 사람이 포함되어 있지 않다면 거짓말 횟수를 업데이트해 준다.
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()
}
profile
어제보다 더 나은 오늘이 되자

0개의 댓글