[BOJ 1043] 거짓말 (C++)
거짓말 (Gold 4) 문제 전체 문제 보기 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 접근법 이 문제에서 진실을 모르는 사람들만 있는 파티의 수를 구해야 한다. 이 문제에서 진실은 같은 파티에 참석한 사람들에게 전파되는 특징이 있다. 파티의 참석자를 노드, 파티의 참석 정보를 인접 노드에 대한 정보, 진실이 전파되는 특징을 인접 노드 탐색으로 본다면 BFS로 풀 수 있는 문제이다. 자료구조 선택 BFS 알고리즘을 활용하여 문제를 풀어본다. BFS로 풀이하기 위하여 다음과 같은 노드를 정의할 수 있다. BFS에서는..