문제 개요
오늘의 코딩 테스트 문제는 백준 1043번 "거짓말"이다. 파티에서 거짓말을 할 수 있는 최대 횟수를 구하는 문제다. 진실을 아는 사람들과 각 파티의 참석자 정보가 주어진다.
문제 분석
핵심은 진실을 아는 사람들의 네트워크를 파악하는 것이다. 직접적으로 진실을 아는 사람뿐만 아니라, 그들과 같은 파티에 참석한 사람들도 결국 진실을 알게 된다.
주요 포인트:
1.
진실을 아는 초기 그룹 파악
2.
파티를 통한 진실 전파 과정 시뮬레이션
3.
거짓말을 할 수 있는 파티 카운트
접근 방식
BFS(너비 우선 탐색)를 활용해 문제에 접근했다. 진실을 아는 사람들을 시작점으로 삼아, 그들이 참석한 파티의 모든 사람들로 탐색을 확장해 나갔다.
1.
진실을 아는 사람들을 큐에 초기화
2.
큐가 빌 때까지 반복:
•
큐에서 한 사람을 꺼내 그 사람이 참석한 모든 파티 확인
•
해당 파티의 모든 참석자를 진실을 아는 그룹에 추가
•
새롭게 추가된 사람들을 큐에 삽입
3.
진실을 아는 사람이 없는 파티 개수 계산
코드 구현
#include <iostream>
#include <queue>
#include <set>
using namespace std;
int main()
{
int N, M;
cin >> N >> M;
queue<int> q;
set<int> people;
vector<set<int>> party_list;
int num, temp;
cin >> num;
for (int i = 0; i < num; i++)
{
cin >> temp;
people.insert(temp);
q.push(temp);
}
for (int i=0; i<M; i++)
{
cin >> num;
set<int> party;
for (int j = 0; j < num; j++)
{
cin >> temp;
party.insert(temp);
}
party_list.push_back(party);
}
while(!q.empty())
{
int target = q.front();
q.pop();
for (int i=party_list.size()-1; i>=0; i--)
{
if (party_list[i].find(target) != party_list[i].end())
{
for (int person : party_list[i])
{
if (people.find(person) == people.end())
{
people.insert(person);
q.push(person);
}
}
party_list.erase(party_list.begin()+i);
}
}
}
cout << party_list.size() << endl;
return 0;
}
C++
복사
구현 과정에서의 고민
처음에는 단순히 set을 사용해 진실을 아는 사람들을 관리하려 했다. 하지만 파티를 통한 진실 전파를 효과적으로 시뮬레이션하기 위해 큐를 도입했다. 이렇게 하면 BFS 방식으로 진실이 퍼져나가는 과정을 자연스럽게 모델링할 수 있었다.
파티 정보를 vector<set<int>>로 관리한 것도 중요한 선택이었다. set을 사용함으로써 쉽게 파티에 진실을 아는 사람이 있는지 검색이 가능했다.
최적화
1.
파티 리스트를 역순으로 순회하며 처리한 파티를 제거했다. 이렇게 하면 이미 처리한 파티를 다시 검사하는 것을 방지할 수 있다.
2.
find() 메소드를 사용해 set 내 원소 존재 여부를 빠르게 확인했다.
회고
이 문제를 통해 그래프 탐색 알고리즘을 실제 상황에 적용하는 방법을 다시 한번 익힐 수 있었다. BFS를 사용해 "정보의 전파"를 모델링하는 것이 효과적이라는 점을 체감했다.
다만, 처음에 문제를 봤을 때 그래프 문제라고 직관적으로 파악하지 못한 점은 아쉽다. 앞으로는 문제를 보고 적절한 알고리즘을 더 빠르게 연결할 수 있도록 연습해야겠다.
