ALGORITHM/BOJ
[BOJ] 1043번 거짓말 (C++)
yegyeom
2021. 12. 27. 13:49
문제 (https://www.acmicpc.net/problem/1043)
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
유니온파인드로 해결한 문제이다.
1. 각 파티에 오는 사람들끼리 연결시킨다. (unionParent)
2. 전체 파티의 인원수만큼 반복문을 돌며 처음 입력받았던 진실을 아는 사람과 연결되었는지 확인한다. (findParent)
2-1. 해당 파티에 진실을 아는 사람과 연결된 사람이 존재한다면? 그 파티에서는 거짓말을 할 수 없으므로 반복문 탈출
2-2. 해당 파티에 진실을 아는 사람과 연결된 사람이 존재하지 않는다면? 정답 증가
가장 도움 되었던 반례! 문제 질문 페이지에 다른 분이 올려주신 건데 덕분에 잘못된 점을 찾았었다.
https://www.acmicpc.net/board/view/72203
[소스코드]
