[CF 1169B] Pairs

[CF 1169B] Pairs - 1500

 

문제 설명 : 

두 개의 정수로 구성된 pair가 총 m개 주어진다. 임의의 정수 2개(x,y)를 선택해서 최소 하나의 정수가 모든 pair에 등장하게 만들 수 있는지 판단하는 문제이다.

 

풀이 : 

정답이 존재하기 위해서는 m개의 pair중에서 임의의 pair 하나를 선택했을 때 둘 중 하나는 반드시 x,y와 동일할 것이다. 그래서 기본 전제로 pair의 0번째 원소(몇 번째 원소인지는 상관없다) 중 하나에 x,y중 하나는 존재한다는 것을 깔아서 이것이 성립할 수 있는지 검증해볼 것이다.

pair의 첫 번째 원소의 first와 second를 각각 x라고 가정하고, 다음과 같은 시행을 한다 : 

m개의 pair에 대해서 두 정수 모두 x와 같지 않다면 need라는 변수의 값을 1 증가시키고, map에 pair의 first와 second값을 1 증가시킨다.

모든 m에 대해서 위 시행을 완료하고 난 뒤에는 최종 need값과 같은 값을 가지는 map의 value값이 있는지 찾아본다. 만약 존재한다면 정답은 YES이고 없다면 NO이다.

위 풀이에 대해서 설명하자면 need라는 변수는 pair의 두 정수가 x와 같지 않을 때마다 증가하는 변수로 y가 커버해야할 pair의 개수를 의미한다. 처음에 우리는 pair[0]의 first와 second를 x로 가정했으므로 그 다음에는 적절한 y를 찾아서 x와 y의 합집합이 모든 m개의 pair를 커버할 수 있는지를 확인해봐야하는 것이다. 임의의 pair에서 둘 중 하나라도 x와 동일하다면 해당 pair는 굳이 y가 커버할 필요가 없지만 둘 다 x와 같지 않다면 반드시 y가 커버해야할 영역이라는 뜻이다. 그 커버해야할 영역의 개수가 변수 need인 것이다. 그리고 map(혹은 30만개 짜리 배열을 써도 무관함)은 y가 될 수 있는 후보군들이다. map의 key값이 커버하고 있는 개수가 value라는 의미이다. 예를 들어 map[1]=3이라면 1이라는 수가 총 3개의 pair를 커버할 수 있다는 의미이다. 그래서 y가 cover 총 개수와 map[key]값이 동일하다면 해당 key값이 y의 자격을 충족하는 것이다.

 

주의할 점 : 

초기 설정한 x가 모든 pair에 대해서 포함되어 있다면 정답은 YES이지만, 그런 경우에 map이 비어있게 되므로 NO라고 판단할 수도 있다. 따라서 처음에 map에 dummy key값(입력으로 들어오는 수의 범위에서 벗어난 값) 하나만 넣어두면 된다.

 

배운 점 : 

난이도는 그리 높지도 않고 디스크립션도 간단한데, 처음에 어떻게 풀어야 하는지 턱 막히는 문제이다. 

정답이 존재한다면 임의의 pair의 first와 second중 최소 하나는 반드시 x,y라는 의미이므로 두 수를 x라고 가정하고 나머지 적절한 y를 찾아나간다는 방식이다.

 

코드 :

const int SIZE=300009;

int a[SIZE],b[SIZE];

int main(){
    int n,m;    scanf("%d %d",&n,&m);

    for(int i=1 ; i<=m ; i++){
        scanf("%d %d",&a[i],&b[i]);
    }

    for(int here:{a[1],b[1]}){
        int need=0;
        map<int,int> mii;

        for(int i=1 ; i<=m ; i++){
            if(here==a[i] || here==b[i]) continue;
            need++;
            mii[a[i]]++;
            mii[b[i]]++;
        }

        mii[-1]=0;
        for(auto &there:mii){
            if(there.second==need){
                printf("YES\n");
                return 0;
            }
        }
    }
    printf("NO\n");

    return 0;
}