BOJ 2988 - 아보가드로

문제 링크 : https://www.acmicpc.net/problem/2988 (P3)

문제 풀이

2번째 줄에 등장하지 않은 수나, 3번째 줄에 등장하지 않은 수의 값이 첫번째 줄에 쓰여있으면 그 줄은 절대로 선택될 수 없다. 그 줄을 지우게 되면 이로 인해서 또 2번째 줄이나 3번째 줄에 등장하지 않는 수가 생길 것이다. 그러면 또 그 수가 첫번째 줄에 적혀있는 줄을 지운다. 이 과정을 반복하면 된다. 

더이상 이 과정을 진행하지 않는다는 것은 첫번째 줄에는 있는데, 두번째 줄이나 세번째 줄에는 없는 수는 없다. 이때 각 줄에 쓰인 수의 갯수는 같으므로, 각 줄에 대해서 쓰여있는 수들의 집합은 셋이 모두 동일할 수 밖에 없게 된다. 이는 문제 해결 조건과 정확히 일치하다.

- 코포에 나올법한 문제. 그냥 생각을 잠깐 하고 proof by ac를 띄웠다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll arr[4][101010];
 
ll idx[101010];
ll cnt1[101010];
ll cnt2[101010];
ll vis[101010];
queue<ll> q;
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld",&n);
    for(i=1;i<=3;i++)
        for(j=1;j<=n;j++){
            scanf("%lld",&arr[i][j]);
            if(i==1) idx[arr[i][j]]=j;
            if(i==2) cnt1[arr[i][j]]++;
            if(i==3) cnt2[arr[i][j]]++;
        }
 
    for(i=1;i<=n;i++){
        if(cnt1[i]==0||cnt2[i]==0){
            vis[i]=1;
            q.push(i);
        }
    }
    ll cnt=0;
    while(!q.empty()){
        cnt++;
        ll x=q.front(); q.pop();
        //printf("%lld ",x);
        x=idx[x];
        //printf("%lld\n",x);
        cnt1[arr[2][x]]--;
        if(cnt1[arr[2][x]]==0&&vis[arr[2][x]]==0){
            vis[arr[2][x]]=1;
            q.push(arr[2][x]);
        }
 
        cnt2[arr[3][x]]--;
        if(cnt2[arr[3][x]]==0&&vis[arr[3][x]]==0){
            vis[arr[3][x]]=1;
            q.push(arr[3][x]);
        }
    }    
    printf("%lld",cnt);
}