C++ 백준 13160 (최대 클리크 구하기)

백준 13160 (최대 클리크 구하기)

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

13160번: 최대 클리크 구하기

---

클리크란 어떤 그래프내에 존재하는 sub 완전그래프이다.

여기서 완전그래프란 모든 노드가 서로 연결되어있는 그래프를 뜻한다.

 

설명

---

문제에서 가져온 그림이다. 

직선들을 쭉 나열했을 때 가장 많이 겹치는 부분에서의 포함되는 숫자를 찾으면 되는 것이다.

위의 경우에는 빨간 세로선일때 1 2 4가 겹쳐지면서 가장 많이 겹쳐질 때 이므로 최대 클리크는 1 2 4가 되는 것이다. 

 

가장 많이 겹쳐질 때는 어떻게 구할까?

간단하다.

위의 예제에서의 인풋은 다음과 같다.

1 3
3 7
7 10
2 5

이때, 각 직선이 열리고 닫힌다고 생각해보면

1(open), 3(close)

3(open), 7(close)

7(open), 10(close)

2(open), 5(close)

으로 표현이 가능하다.

그렇다면 모든 숫자를 오름차순으로 정렬한 후, 돌면서 open이 가장 많을 때가 최대클리크 일것이다. (생각해보면 당연함)

 

이때, 만약 같은 숫자라면 open인 숫자를 앞에 둬야 정확한 답을 찾을 수 있다.

 

이렇게 최대클리크의 수는 간단하게 찾을 수 있는데 문제는 그 때 포함하는 노드의 번호이다.

여러 방법이 있겠지만 가장 간단한 방법은 다음과 같다.

위 과정에서 open이 가장많을 때 빨간줄의 x좌표를 가지고 있는다.

그리고 pair를 다시 처음부터 돌면서 해당 x좌표를 포함하는 구간의 노드를 저장하면 된다.

 

구현

---

#include <iostream>
#include <vector>
#include <algorithm>
#define pib pair<int, bool>
using namespace std;
int n;
int a,b;
vector <pib> v;
vector <pair<int, int>> input;
bool comp(pib &a, pib &b){
	if(a.first==b.first){
		if(a.second) return true;
		else return false;
	}
	return a.first<b.first;
}

int main(){
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int curr=0;
	cin>>n;
	int ans=0;
	int position;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		v.push_back({a,true});
		v.push_back({b,false});
		input.push_back({a,b});
	}
	sort(v.begin(),v.end(), comp);
	for(int i=0;i<v.size();i++){
		if(v[i].second) curr++;
		else curr--;
		if(curr>ans){
			ans = curr;
			position = v[i].first;
		}
	}
	cout<<ans<<"\n";
	for(int i=0;i<input.size();i++){
		if(input[i].first<=position && input[i].second>=position) cout<<i+1<<" ";
	}
	return 0;
}