문제 링크입니다: https://www.acmicpc.net/problem/1043
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민
www.acmicpc.net
N과 M이 최대 50이기 때문에 시간복잡도가 O(N^3)이여도 무난하게 풀 수 있는 문제였습니다.
알고리즘은 아래와 같습니다.
1. 우선 진실을 아는 사람들을 revealed 배열을 통해 표시하고
2. 각 파티에 참석한 사람들을 participatedParty 배열에 [파티][사람] 형식으로 표시해주고
3. 참석한 사람이 진실을 아는 사람이고 해당 파티가 revealedParty에 아직 표시되어 있지 않다면 revealedParty에 표시를 해주고 queue에 해당 파티 인덱스 번호를 enqueue 해줍니다.
4. 이후에는 참석한 사람들이 겹치는 파티들을 양방향으로 relatedParties 벡터를 통해 기록합니다.
5. queue에는 현재 진실을 아는 사람이 참여한 해당 파티가 있으므로 해당 큐를 이용하여 해당 파티와 연관된 파티들을 모두 표시해줍니다.
6. 마지막으로 진실을 아는 사람과 연관되지 않은 파티 즉, revealedParty 인덱스가 false인 개수를 출력해줍니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 3079번 입국심사 (0) | 2020.03.08 |
|---|---|
| 백준 10868번 최솟값 (0) | 2020.03.08 |
| 백준 11328번 Strfry (0) | 2020.03.02 |
| 백준 1267번 핸드폰 요금 (0) | 2020.03.01 |
| 백준 10804번 카드 역배치 (0) | 2020.03.01 |