1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
이 문제는 유니온 파인드+BFS 또는 비트마스킹을 통해 해결할 수 있다. 유니온 파인드를 모른다면 본 블로그의 해당 포스팅을 읽어보길 바란다. 아래의 그림을 보자
문제에 주어진 바와 같이, 파티 3개를 구성했다. 그리고 파티에 참가하는 인원들을 모두 엮어서 그래프로 표현할 수 있다.
2-3-4는 같은 파티에 참가하므로 사이클을 이루고, 1과 2가 같이 파티에 참가하므로 연결된다. 가장 중심에 있는 2가 만약에 진실을 알고 있다면, 그래프로 보는 바와 같이, 1,3,4에게 진실이 전파되어 모두가 진실을 알게 되고, 참가할 수 있는 파티는 0이 된다.
위의 예시는 문제의 조건과는 다르지만, 문제 이해에 도움을 주기 위해 넣었다. 즉 그래프로 친구관계를 형성하고, BFS 등의 탐색을 통해 진실을 전파할 수 있다. 그리고 해당 정점이 진실을 아는지를 확인하기 위해서는 매번 초기 진실 인지자까지 그래프 순회를 하는 것이 아니라, 유니온 파인드를 통해 루트값을 업데이트해두는 것이다.
아래의 코드를 보자.
temp = [int(e) for e in si().split()]
temp = temp[1:]
parties.append(temp)
for i in range(len(temp)-1):
for j in range(1, len(temp)):
graph[temp[i]].append(temp[j])
graph[temp[j]].append(temp[i])
if len(temp) > 1:
for i in range(len(temp)-1):
union(temp[i], temp[i+1])먼저 파티에 참여하는 인원들 간에 그래프 연결을 해준다. 그리고 파티에 참여하는 인원이 2인 이상이면 그들을 union으로 연결해준다.
def union(a, b):
q = deque()
aroot = find(a)
if aroot in set_ppl_truth:
roots[b] = aroot
q.append(b)
visited[b] = True
while q:
curr = q.popleft()
for nxt in graph[curr]:
if not visited[nxt]:
visited[nxt] = True
q.append(nxt)
union(a, nxt)
return위와 같이, a가 진실을 아는 사람들의 집합안에 포함된다면, b의 루트가 a의 루트가 되고, (여기서 다시 중요한 것은 b의 루트는 a가 되는 것이 아니라, a의 루트가 바로 연결된다는 점이다!) 그리고 b의 루트가 변경되었으므로, b와 연결된 모든 정점들을 BFS로 탐색하여 루트 업데이트를 해준다.
이것이 필요한 이유는 첫번째 미팅에 참석한 사람들이 모두 진실을 몰랐다고 했을 때, 그 때의 인원들 중 한 명이 두 번째 미팅에 참석하여 진실을 들었을 경우를 해결하기 위함이다. 첫 번째 미팅에 오는 사람들끼리는 그래프로 연결이 되어있고, 두 번째 미팅에서 그 사람 중 한 명이 '진실화'되었다면, BFS를 통해 첫 번째 미팅의 인원을 모두 진실화 할 수 있기 때문이다.
그렇게 모든 인원들의 '진실화'를 완료했다면 아래와 같이 파티정보를 루프로 돌면서 해당 파티에 참석할 수 있는지 없는 지를 세어주기만 하면 된다.
for party in parties:
flag = False
for person in party:
if find(person) in set_ppl_truth:
flag = True
break
if not flag:
cnt += 1
이번에는 다른 방법을 소개하고자 한다. 바로 비트마스킹을 통한 풀이다.
위와 같이 유니온 파인드로 문제를 해결할 수도 있지만, 필자는 이 문제를 처음 접하였을 때, 유니온 파인드라는 것 자체를 몰랐다. 그래서 비트마스킹으로 풀었다. 문제에서 파티에 참여할 인원의 수가 50명이라는 점에 착안하였다.
unsigned int의 경우 32개의 비트를 가지는데, 필자는 unsigned int 2개를 사용하여 64개의 비트를 확보하였다. 아래와 같이, 구조체를 통해 64개의 비트를 확보하였다. 즉, 64명을 표현할 수 있게 된 것이다.
struct ppl
{
unsigned int p1;
unsigned int p2;
};signed int는 가장 앞에 부호비트가 있어서 31개만 사용할 수 있지만, unsigned int는 32개를 모두 쓸 수 있다.
그리고 이제 진실을 아는 사람들의 비트를 켜주면 된다.
16번이 진실을 아는 사람이라면,
ppl.p1 |= 1 << pn 를 통해 해당 비트를 켜준다.
그리고 각 파티별로 똑같은 형태의 구조체를 두어, 참석인원들 간 진실 전파를 해줄 수 있다.
struct meet
{
unsigned int p1;
unsigned int p2;
};하지만 여기는 사용법이 약간 다르다. 진실을 아는 사람의 비트를 켜는 것이 아니라, 파티에 참석하는 사람들의 비트를 켜는 것이다.
이제 아래와 같이, 파티에 참석한 사람중에 진실을 아는 사람이 있다면 비트의 OR연산을 통해 파티 참석 인원 전원의 비트를 켜주는 것이다.
if (meetings[i].p1 & ppl.p1 || meetings[i].p2 & ppl.p2)
{
ppl.p1 |= meetings[i].p1;
ppl.p2 |= meetings[i].p2;
}이것을 통해 O(1)로 진실을 아는 사람들 업데이트를 완료할 수 있다!
그리고 주의할 점은 이후의 파티에서 진실 전파가 이루어졌다면 첫 번째 파티부터 다시 봐야 한다는 점이다 ㅠㅠ
그래서 파티를 순회하는 루프에서 파티번호를 -1로 초기화해주는 것이 중요하다 (그래야 ++되어 0부터 보기 때문)
<주요 내용>
유니온 파인드, BFS, 비트마스킹
<코드>
유니온 파인드 + BFS를 활용한 파이썬 코드
더 좋은 풀이가 있을 수도 있고, 본 코드가 정리가 안된 부분에 대해서는 양해 부탁드린다.
import sys
from collections import deque
si = sys.stdin.readline
graph, set_ppl_truth = [[] for _ in range(50+1)], set()
roots = [i for i in range(50+1)]
visited = [False for _ in range(50+1)]
def union(a, b):
global roots, set_ppl_truth, graph, visited
q = deque()
aroot = find(a)
if aroot in set_ppl_truth:
roots[b] = aroot
q.append(b)
visited[b] = True
while q:
curr = q.popleft()
for nxt in graph[curr]:
if not visited[nxt]:
visited[nxt] = True
q.append(nxt)
union(a, nxt)
return
broot = find(b)
if broot in set_ppl_truth:
roots[a] = broot
q = deque()
q.append(a)
visited[a] = True
while q:
curr = q.popleft()
for nxt in graph[curr]:
if not visited[nxt]:
visited[nxt] = True
q.append(nxt)
union(b, nxt)
return
roots[b] = aroot
def find(a):
if roots[a] == a:
return a
roots[a] = find(roots[a])
return roots[a]
def main():
global roots, set_ppl_truth, graph, visited
n, m = [int(e) for e in si().split()]
info_ppl_truth = [int(e) for e in si().split()]
set_ppl_truth = set(info_ppl_truth[1:])
parties = []
while m:
m -= 1
temp = [int(e) for e in si().split()]
temp = temp[1:]
parties.append(temp)
for i in range(len(temp)-1):
for j in range(1, len(temp)):
graph[temp[i]].append(temp[j])
graph[temp[j]].append(temp[i])
if len(temp) > 1:
for i in range(len(temp)-1):
union(temp[i], temp[i+1])
cnt = 0
for party in parties:
flag = False
for person in party:
if find(person) in set_ppl_truth:
flag = True
break
if not flag:
cnt += 1
print(cnt)
if __name__ == '__main__':
main()
비트마스킹을 활용한 C++ 코드
#include <iostream>
// #include <unordered_set>
#include <set>
#include <algorithm> //sort
#include <cstring> //memset, use 0 or -1
#define endl '\n'
using namespace std;
// unordered_set<int> visited;
set<int> visited;
const int Max = 50 + 1;
int n, m, t, k, pn, on, cnt;
// int ppl[Max];
struct meet
{
unsigned int p1;
unsigned int p2;
};
typedef struct meet meet;
meet meetings[Max - 1];
//ppl who know the truth
struct ppl
{
unsigned int p1;
unsigned int p2;
};
typedef struct ppl ppl;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
ppl ppl;
ppl.p1 = 0;
ppl.p2 = 0;
// meet meet;
cin >> n >> m >> t;
for (int i = 0; i < t; ++i)
{
cin >> pn;
if (pn < 32)
ppl.p1 |= 1 << pn;
else
ppl.p2 |= 1 << (pn - 32);
}
for (int j = 0; j < m; j++)
{
cin >> k;
for (int i = 0; i < k; i++)
{
cin >> pn;
if (pn < 32)
meetings[j].p1 |= 1 << pn;
else
meetings[j].p2 |= 1 << (pn - 32);
}
}
if (!t)
cout << m << endl;
else
{
while (visited.size() != m)
{
for (int i = 0; i < m; ++i)
{
// unsigned int& pplP1=ppl.p1;
// unsigned int& pplP2=ppl.p2;
auto met = visited.find(i);
if (met == visited.end())
{
if (meetings[i].p1 & ppl.p1 || meetings[i].p2 & ppl.p2)
{
ppl.p1 |= meetings[i].p1;
ppl.p2 |= meetings[i].p2;
visited.insert(i);
i = -1; //important!!!
}
else if (on)
{
cnt++;
visited.insert(i);
}
}
}
on = 1;
}
cout << cnt << endl;
}
return 0;
}
