[백준] BOJ 3018 : 캠프파이어

https://www.acmicpc.net/problem/3018

3018번: 캠프파이어

 

문제의 조건을 요약하면 아래와 같습니다.

 

1. E일간 캠프파이어가 진행됩니다.

2. 선영이가 캠프파이어 참여하는 날에는 새로운 노래가 하나 만들어집니다. 그 날에는 사람들은 서로 노래들을 공유 안하고 그 노래만 부릅니다.

3. 선영이가 캠프파이어에 참여하지 않는 날에는 캠프파이어 하는 사람들끼리 본인들이 알고있는 노래들을 모두 공유합니다.

4. 문제에서는 선영이를 포함해서 모든 노래를 알고 있는 사람이 몇 명인지를 구해야 합니다.

 

저는 이 문제를 처음 보았을 때 E의 범위가 최대 50밖에 안 되는 것에 집중하였습니다. 또한, 선영이가 나온 날에만 노래가 탄생하고 안 나온 날에는 서로 공유하는데, 이를 어떻게 쉽게 구현할지도 생각해보았습니다. 그러다가 long long의 범위가 64비트로 표현되는 걸 기억해냈습니다. 

 

그렇다면 각 노래들을 어느 날짜에 나왔는지로 판별할 수 있고, 날짜가 최대 50일이므로 long long integer을 활용한다면 각 사람별로 어느 날짜에 생성된 노래를 알고 있는지의 여부를 알 수 있습니다. i번째 비트가 1이면 i번째 날에 생성된 노래를 알고 있다고 생각하면 됩니다. 그러면 각 날짜마다 노래가 생성되는 것과 공유하는 것을 이렇게 처리할 수 있습니다.

• 생성 : 선영이가 나온 날에는 나온 사람 모두에 대해서 해당 날짜에 대한 비트를 1로 설정합니다.
• 공유 : 선영이가 안 나온 날에는 나온 사람들끼리 모두 bitwise OR를 하고 모든 사람이 해당 값을 갖습니다.

문제의 정의에 따라서 선영이는 모든 생성된 노래를 항상 알고 있으므로, 이후에 모든 사람들에 대해서 선영이가 알고 있는 노래들을 표현한 정수랑 본인의 정수랑 같은지 비교해서 같으면 출력하면 됩니다.

 

코드는 아래와 같습니다. 시간복잡도를 계산해보면 각 캠프파이어 날마다 O(N)만큼의 operation을 해야하고, 마지막에 O(N)번 선영이와 값이 같은지를 판단해야하므로, 총 시간복잡도는 O(NE + N)이 됩니다. 

 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  ll N, E;
  cin >> N >> E;

  vector<ll> know(N+1,0);
  for(ll l =0; l<E; ++l){
    ll k;
    cin >> k;
    vector<ll> v(k);
    bool has_one = false;
    for(int i =0; i<k; ++i){
      cin >> v[i];
      if(v[i] == 1) has_one = true;
    }
    
    if(has_one){
      for(int i =0; i<k; ++i){
        know[v[i]] |= ((ll)1 << l);
      } // 나온 사람들 모두에게 해당 날짜에 대한 비트를 1로 설정
    } // 선영이가 존재하는 경우
    else {
      ll val = 0;
      for(int  i =0; i<k ;++i){
        val |= know[v[i]];
      } // 나온 사람들 모두 OR
      for(int  i =0; i<k ;++i){
        know[v[i]] |= val;
      } // 나온 사람들을 모두 OR한 값으로 전부 설정
    } // 선영이가 없는 경우
  }

  ll cnt = know[1];
  for(int i =1; i<=N; ++i){
    if(know[i] == cnt) cout << i<<"\n";
  } // 선영이랑 동일한 값을 가지면 모든 노래를 아는 사람임.
  // i = 1 -> N 이렇게 보기에 그냥 출력하면 오름차순으로 출력됨.

  return 0;
} // Bitmasking

 

이 문제의 정해는 사실 Hashmap + Implementation이라고 합니다. 다만, 개인적으로는 이러한 다른 방법으로도 풀어보는 것도 매우 공부가 된다고 생각합니다. (사실 제가 푼 방법으로 푸는 사람들도 꽤 있습니다.) Bitwise operation으로 풀리는 풀이가 재밌었기에 한 번 공유해보았습니다. 그리고 이렇게 실버 문제들도 이 문제부터 하나하나씩 풀이를 적을 수 있으면 좋겠네요.