[백준] 3088 화분 부수기

 

오래 고민한 문제다..!

이런거 참 생각을 잘 못하는거같다

 

어떤 화분을 깨면 화분에 해당하는 숫자가 오른쪽에 임의에 화분에 있다면 그 화분도 깰수있다

계속 연속적으로 이어져간다

 

자 생각을 해보자..!

 

맨 처음 화분은 무조건 깨야만한다. 안그러면 아무도 깨주지 않으므로..!

그럼 맨 처음 화분에 포함되는 수를 앞으로 만난다면 그 화분도 무조건 깨져야한다

그럼 입력받으면서 처리할 수 있다..!

 

화분을 깨지는 수를 계속 저장해가며 하나라도 가지고 있으면 깨버리자!

소스는 참 짧다!

 

처음에는 set을 썼는데 그럼 시간이 너무 오래 걸린다

배열을 이용하자

 

소스코드

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
int n,ans;
bool check[1000001];
int main(){
    scanf(" %d",&n);
    for(int i=0;i<n;i++){
        int a,b,c; scanf(" %d %d %d",&a,&b,&c);
        if(!check[a] && !check[b] && !check[c]) ans++;
        check[a]=check[b]=check[c]=true;
    }
    printf("%d\n",ans);
}