문제 설명
우리 마을에는 여러 명의 주민들이 있습니다. 이 주민들 중에서 일부는 자신이 하고 싶은 말을 하기 위해 거짓말을 합니다. 과연 우리가 알고 있는 정보 중에서 거짓말쟁이를 판별할 수 있을까요?
문제 정리
주어진 N명의 주민들이 자신의 이웃들에 대한 정보를 제공합니다. 각 주민은 자신이 이웃으로 생각하는 주민들이 누구인지, 그런 주민들이 자신에 대해 어떤 말을 했는지에 대한 정보를 입력받습니다. 우리는 각 주민이 자신을 기만하고 있는지를 판별하려고 합니다. 결국 이 문제는 주민들의 진술이 서로 일치하는지를 파악하는 것입니다.
입력 형식
첫 번째 줄에 주민의 수 N이 입력됩니다. 이후 N줄에 걸쳐 각 주민의 인덱스, 그 주민이 생각하는 이웃의 수 M, 그리고 M명의 이웃에 대한 정보가 흩어져서 입력됩니다. 이웃의 정보는 각각 그 이웃의 인덱스와 해당 인덱스에 대한 진술이 거짓인지 진실인지에 대한 정보가 포함됩니다.
출력 형식
각 주민이 거짓말쟁이인지 아닌지를 판단하여, YES 또는 NO로 결과를 출력합니다.
예시 입력
3
0 2 1 1 0
1 1 0
2 1 1
예시 출력
NO
NO
YES
문제 풀이 과정
이 문제를 해결하기 위해 우리는 다음과 같은 과정을 따릅니다.
1단계: 문제 이해
주민들의 발언에서 진실과 거짓을 판별하기 위해서는 각 주민이 이웃에 대해 한 말을 바탕으로 서로 다른 주민의 진술 간의 일관성을 확인해야 합니다. 예를 들어, A라는 주민이 B를 이웃이라고 주장하는 경우, B가 A를 거짓말이라고 주장하면, A가 진짜 거짓말쟁이라는 것을 알 수 있습니다.
2단계: 데이터 구조 설계
이 문제를 해결하기 위해 배열 또는 리스트를 이용하여 주민들의 정보를 저장하고 관리할 수 있습니다. 각 주민에 대한 정보를 담기 위해 각 주민의 인덱스 (0부터 시작)와 이웃의 정보를 담는 리스트를 사용하는 방법이 적절합니다. 이를 위해 Pair 클래스를 사용하여 주민 정보를 구성하는 것도 좋습니다.
3단계: 알고리즘 설계
주어진 주민들에 대한 정보를 수집한 후, 우리는 이 정보를 바탕으로 주민들의 발언이 서로 일치하는지를 판단할 것입니다. 이를 위해 다음의 알고리즘을 설계할 수 있습니다.
1. 주민의 수 N을 입력받는다.
2. 각 주민의 정보를 담기 위해 리스트를 초기화 한다.
3. 주민 각각에 대하여 이웃의 정보와 진술을 입력받아 저장한다.
4. 각 주민의 이웃의 진술이 서로 일치하는지를 체크한다.
5. 일치하지 않는 경우 해당 주민을 거짓말쟁이로 판별한다.
6. 결과를 출력한다.
4단계: 코틀린 코드 구현
이제 본격적으로 알고리즘을 코틀린 코드로 구현합니다. 아래는 해당 문제를 해결하기 위한 코틀린 코드입니다.
data class Neighbor(val index: Int, val isLiar: Boolean)
fun findLiar(N: Int, statements: List>): List {
val result = MutableList(N) { "NO" }
for (i in 0 until N) {
val neighbors = statements[i]
for (neighbor in neighbors) {
val expectedTruth = !neighbor.isLiar
if (expectedTruth && result[neighbor.index] == "YES") {
result[i] = "YES"
break
} else if (!expectedTruth && result[neighbor.index] == "NO") {
result[i] = "YES"
break
}
}
}
return result
}
fun main() {
val N = readLine()!!.toInt()
val statements = mutableListOf>()
for (i in 0 until N) {
val input = readLine()!!.split(" ").map { it.toInt() }
val M = input[1]
val neighbors = mutableListOf()
for (j in 0 until M) {
val neighborIndex = input[2 + j * 2]
val liar = input[3 + j * 2] == 1
neighbors.add(Neighbor(neighborIndex, liar))
}
statements.add(neighbors)
}
val result = findLiar(N, statements)
for (r in result) {
println(r)
}
}
5단계: 테스트 및 검증
코드가 완성되었으면 다양한 테스트 케이스를 통해 코드를 검증해야 합니다. 최소 입력, 최대 입력, 다양한 시나리오를 통해 코드의 전반적인 안정성과 신뢰성을 확인할 필요가 있습니다.
결론
이번 문제를 통해 코틀린에서 알고리즘 문제를 어떻게 접근하고 해결하는지를 배웠습니다. 주민들의 진술을 분석하여 진실과 거짓을 규명하는 과정은 문제 해결에 필요한 논리적 사고를 발전시키는 데 큰 도움이 됩니다. 또한, 복잡한 문제를 단순한 데이터 구조와 알고리즘 변형을 통해 접근하는 방법을 익히게 되어 많은 도움이 되었으리라 생각합니다.
이제 여러분도 조심스럽게 거짓말쟁이를 찾아내는 알고리즘을 구현해 보시기 바랍니다!