문제 (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
[소스코드]
'ALGORITHM > BOJ' 카테고리의 다른 글
| [BOJ] 1990번 소수인팰린드롬 (C++) (0) | 2021.12.27 |
|---|---|
| [BOJ] 1747번 소수&팰린드롬 (C++) (0) | 2021.12.27 |
| [BOJ] 15927번 회문은 회문아니야!! (C++) (0) | 2021.12.27 |
| [BOJ] 7490번 0 만들기 (C++) (0) | 2021.12.21 |
| [BOJ] 17070번 파이프 옮기기 1 (C++) (0) | 2021.12.21 |