[백준 13160번] 최대 클리크 구하기

link : https://www.acmicpc.net/problem/13160

최대 클리크 구하기 성공 스페셜 저지

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	284	120	98	42.609%

문제

그래프 이론에서 클리크란, 완전 그래프인 부분 그래프를 의미한다. 즉, 정점으로 이루어진 집합 중 모든 두 정점 사이에 간선이 있는 집합을 의미한다. 최대 클리크는 그러한 집합 중 크기가 가장 큰 집합을 말한다. 일반적인 그래프에서 최대 클리크를 구하는 문제는 NP-hard 이다.

N개의 구간이 있다. i번 구간의 시작점은 Si, 끝점은 Ei이며, 어떤 두 구간이 한 점 이상을 공유하면 이 두 구간을 ‘겹친다’고 표현한다. 이때 우리는 구간 그래프를 정의할 수 있다. 구간 그래프란, N개의 정점이 있고, i번 구간과 j번 구간이 겹칠 때, i번 정점과 j번 정점 사이에 간선이 존재하는 그래프다. 만약 두 구간이 겹치지 않는다면 i번 정점과 j번 정점 사이에 존재하는 간선은 없다.

예를 들어 위와 같이 N개의 구간이 있을 때 이를 구간 그래프로 나타내면 아래와 같다.

이때 이 구간 그래프의 최대 클리크는 {1, 2, 4}이다.

N개의 구간이 주어졌을 때, 이에 대한 구간 그래프의 최대 클리크를 구하시오.

입력

입력의 첫 줄에는 구간의 수를 나타내는 자연수 N(1≤N≤300,000)이 주어진다. 다음 N개의 줄에 각 구간의 시작점과 끝점을 나타내는 두 자연수 Si, Ei가 공백으로 구분되어 주어진다. (1 ≤ Si < Ei ≤ 109)

출력

첫 줄에 최대 클리크의 크기 s를 출력한다. 둘째 줄에는 클리크에 있는 정점들의 번호 s개를 공백으로 구분하여 출력한다. 출력 순서는 상관없으며, 만약 최대 클리크가 여러 가지인 경우 그 중 아무거나 출력한다.

예제 입력 1 

4
1 3
3 7
7 10
2 5

예제 출력 1 

3
1 4 2

UCPC를 준비하면서 해결해본 문제이다.

이것도 기업 코딩 테스트를 풀면서 봤던 문제와 매우 유사했다.

겹치는 구간을 알기 위해서 시작점에는 '1' 태그를 붙여주고 끝점에는 '-1' 태그를 붙여줬다.

모두 넣은 후 sort해 0~N까지 모두 돌았고, 태그를 계속 더해주면서 최대값 max의 위치를 저장한다.

후에 나머지 처리를 해주면 O(N)의 시간 내에 해결이 가능하다.

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, max_num, u, a,b, position;
vector<pair<int,int>> coord;
vector<pair<int,int>> ary;
 
int main(){
 
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    for(int i=0; i<N; i++){
        cin >> a >> b;
        coord.push_back({a,-1});
        coord.push_back({b,1});
        ary.push_back({a,b});
    }
 
    sort(coord.begin(), coord.end());
 
    for(int i=0; i<2 * N; i++){
        u += coord[i].second;
        if(u < max_num){
            max_num = u;
            position = coord[i].first;
        }
    }
 
    cout << -max_num << "\n";
 
    for(int i=0; i<N; i++){
        if(ary[i].first <= position && ary[i].second >= position) cout << i+1 << " ";
    }
 
    return 0;
}