[BOJ] 1043 - 거짓말

문제 출처

[BOJ] 1043 - 거짓말

 

풀이

다양한 풀이 방법이 존재하는 것 같은데 저는 그래프를 만들고 bfs로 탐색하는 방법으로 풀었습니다.

 

지민이가 모든 파티에 참여하는데 그 중 과장된 이야기를 할 수 있는 파티를 찾는 문제였습니다.

 

파티에는 지민이 뿐만아니라 진실을 알고 있는 사람도 참여하기 때문에 진실을 알고 있는 사람이 참여하는 파티에서는 과장된 이야기를 할 수 없습니다. 그리고 그 파티에 참여한 진실을 아는 사람을 제외한 다른 사람들 또한 진실을 듣게 되기 때문에 그 사람들이 참여한 다른 파티에서도 과장된 이야기를 할 수 없습니다.

 

우선 파티에 참여한 사람들을 양방향 그래프로 연결시켜 주었습니다. 모든 파티를 그렇게 한 후 진실을 알고 있는 사람들을 큐에 집어넣고 만들어진 그래프를 bfs를 돌려 check배열로 진실을 아는 사람들을 체크합니다. 

 

check 배열에 체크된 사람들이 모두 포함되지 않은 파티의 경우를 세 결과를 출력해주었습니다.

 

코드

small-j/Algorithm