KOI 2017 중등부 해설

1. 방 배정하기

2019/10/03 - [koi해설] - KOI 2017 초등부 해설

 

2. 곡선 자르기

문제는 단순해 보였지만 아이디어를 잡는데 오래 걸렸다. 각 봉우리사이 포함관계를 확인하면 쉽게 풀리지만 그럴 경우 O(N^2)이다. 시간내에 해결하려면 O(NlogN)또는 O(N)이어야한다는 것에서 정렬 아이디어가 떠올랐다.

각 봉우리의 시작점과 끝점을 pair로 저장한다. 그 후에 pair쌍을 정렬한다. 왼쪽에서부터 하나씩 확인하는데

가장 바깥쪽의 봉우리의 오른쪽 점의 좌표(outmax), 가장 안쪽 봉우리의 오른쪽 좌표(inmax)를 저장한다.

포함하지 않는 봉우리 개수 p

포함되지 않는 봉우리 개수 q

검은 색은 이전까지의 봉우리이고 파란색은 이번에 체크할 봉우리이다.

case1) a>outmax

새 봉우리가 나타났으므로 p,q하나씩 증가

outmax=b

inmax=b

 

case2) oumax>a>inmax

q만 하나 증가

inmax=b로 초기화

case3) a<inmax

p,q변화 없음

inmax=b 초기화

 

여러번 틀렸는데 그 이유는 봉우리의 좌표쌍을 저장하는데 실수했기 때문이다. y=0 기준 아래에서 위로 올라가는 지점부터 봉우리 좌표쌍을 저장하고 그 지점부터 N개의 점을 따라 저장하면 된다.

 

코드...

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;

typedef pair<int,int> P;
vector<P> v;
int N;
int main(){
	cin>>N;
	int a[2];
	int k=0;
	int x[1000000],y[1000000];
	for(int i=0;i<N;i++){
		scanf("%d %d",&x[i],&y[i]);
	}
	int i=0;
	while(1){
		int y1=y[i];
		int y2=y[(i+1)%N];
		if(y1<0 && y2>0) break;
		i++;
	}
	for(int j=i;j<i+N;j++){
		int x1=x[j%N];
		int y1=y[j%N];
		int x2=x[(j+1)%N];
		int y2=y[(j+1)%N];
		if((y1>0 && y2<0)||(y1<0 &&y2>0)){
			a[k++]=x1;
			if(k==2) {
				sort(a,a+2);
				v.push_back(P(a[0],a[1]));
				k=0;
			}
		}
	}
	sort(v.begin(),v.end());
	int len=v.size();
	int outmax=-1000000100;
	int inmax;
	int outsi=0;
	int insi=0;
	for(int i=0;i<len;i++){
		//가장 밖의 사각형 등장
		if(v[i].first>outmax){
			outsi++;
			insi++;
			outmax=v[i].second;
			inmax=v[i].second;
		}
		//현재 확인하는 사각형의 맨 오른쪽
		else if(v[i].first>inmax){
			inmax=v[i].second;
			insi++;
		}
		else{
			inmax=v[i].second;
		}
	}
	cout<<outsi<<" "<<insi;
	return 0;
}

 

3. 줄서기

2019/10/03 - [koi해설] - KOI 2017 초등부 해설

 

4. 산만한 고양이

본 풀이는 koosaga님의 풀이를 보고 공부한 내용을 정리한 것이다.

문제의 핵심은 정점 i와 연결된 간선을 제거했을 때 몇 개의 컴포넌트로 나뉘는지 학인하는 것이다.

관련 내용은 bcc에 대해서 공부하면 좋을 것 같다.

https://m.blog.naver.com/kks227/220802704686

https://koosaga.com/76

 

전체 정점 개수= $n$

전체 간선 개수= $m$

정점 $i$와 연결된 간선 수= $v[i]$

정점 $i$와 인접한 간선을 제거했을때 쪼개진 컴포넌트의 개수를 $component[i]$라 했을 때

각 컴포넌트가 tree일 필요충분 조건은

 $$n-component[i]=m-v[i]$$

이다.

그림을 그리면 저 수식이 쉽게 와닿을 것이다.

 

이제 dfs 트리를 그리면서 각 정점에서 도달할 수 있는 가장 낮은 방문 순서가 저장된 정점을 찾을 것이다.

이 내용의 설명은 코드로 대체한다.

한가지 주의할 점은 루트인지 아닌지에 따라서 $component$수의 차이를 생각해야 한다는 것이다.

• 루트의 경우: 끊어진 컴포넌트 수에서 $1$만큼만 더 추가한 것이 최종 
• 루트가 아닌 경우: 끊어진 컴포넌트 수에서 $2$만큼 더 추가한 것이 최종

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<queue>
#include<utility>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<cmath>
#include<time.h>
using namespace std;

int N,M;
int cnt;
vector<int> adj[300001];
int low[300001];
int discovered[300001];
int component[300001];

void dfs(int here,int prev){
	discovered[here]=low[here]=++cnt;
	for(int next:adj[here]){
		if(next==prev) continue;
		if(discovered[next]==0){
			dfs(next,here);
			low[here]=min(low[here],low[next]);
			//here점을 제거했을 때 component하나 추가
			if(low[next]>=discovered[here]) component[here]++;
		}
		else{
			low[here]=min(low[here],discovered[next]);
		}
	}
	if(here==1) component[here]+=1;
	else component[here]+=2;
}

int main(){
	cin>>N>>M;
	for(int i=0;i<M;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1,0);
	long long ans=0;
	for(int i=1;i<=N;i++){
		if(N-component[i]==M-adj[i].size()) ans+=i;
	}
	cout<<ans;
	return 0;
}

 

 

 

---

 

---

---

밑에는 다른 풀이이다.

예전에 전명우님의 풀이를 보고 공부한 내용이다 (출처: 전명우님 ) 

내 글을 다시 봐도 무슨 말인지 너무 헷갈리게 적었다. 

다른 사람에게 도움이 될지는 모르겠지만 예전에 내가 그만큼 못했다는 것이니 반성의 의미로 지우지는 않아야겠다.

~~~~~~~

 

아무리 오래 생각해도 풀기 힘들었다. 가장 기본적인 생각은 하나씩 점을 제거하고 cycle이 존재하는지 확인하는 작업이지만 그럴경우 O(NM)이 나온다. 거의 일주일을 고민하고 결국 블로그를 읽고 공부했다.(감사합니다) 아이디어는 직관적이지만 구현이 쉽지 않아 보였다. 

맨 아래의 코드는  전명우님 코드의 변수명만 바꾼 거의 그대로이다.

 

먼저 1번 점부터 시작해서 dfs를 할 것인데 각 점의 방문 순서를 저장하자. 나중에 backedge판단여부에 이용된다.

dfs spanning tree에서 backedge는 세 가지 가능성이 있다. 이때 index가 헷갈렸는데 그래서 명확하게 적었다.

아래의 그림과 같이 dfs spaninng tree를 구성했을 때  i를 루트로 하는 서브트리를 I, i의 자손노드 t를 루트로 하는 서브트리를 T라 하자. 아래 처럼 t를 기준으로 센 backedge이다.(i를 지워야하는지 판단여부는 t에 달려있기 때문이다)

 

1) T에서 T로 가는 backedge: inback[t]

2) T에서 i로 가는 backedge: parentback[t]

3) T에서 P(그림)로 가는 backedge: upback[t]

4) T에서 출발하는 backedge: allback[t]

inback[t]+parentback[t]+upback[t]=allback[t]

 

이 때 각 노드 i의 upback수를 카운트하는 것보다 allback을 카운트하는 것이 쉬우므로 allback을 카운트하자.

결국 구하고자 하는 i는 다음중 하나이다.

 

i를 삭제했을 때

1) i의 자손노드(t)가 루트인 서브트리(T)에 대해 inback[t]=0이어야 한다.

2) T의 upback[t](=allback[t]-parentback[t]-inback[t])이 2개 이상있으면 안된다.(cycle생성됨)

3) P->P의 backedge가 있으면 안된다. 즉, 전체 그래프의 backedge 수(=N-(M-1) )와 I의 모든 backedge(inback[i])의 수가 같아야한다. 

위의 논리에 의해 inback, allback,parentback의 수만 잘 세주면 된다는 것을 알게되었다.

dfs하면서 u->v로 가는 backedge가 나올 때마다 inback[v]++, allback[u]++를 해주는데 

i점에 대해 업데이트 과정은 다음과 같다.

1) parentback[t]= 각 t에 대해 dfs(t)후의 inback[i]와 update전의 inback[i] 차이의 합

 

dfs(t)를 해주면 T에서 i로 가는 backedge가 있을 경우만 inback[i]가 증가하기 때문이다.

위의 index가 t임에 유의하자

 

2) inback[i] 증가량= 각 t에 대해 dfs(t)후의 inback[t]값의 합

 

dfs(t)를 하면서 T에서 i로 가는 backedge수만틈 inback[i]가 증가되었으므로 T->T의 backedge만 더해주면 된다.

 

3) allback[i] 증가량= 각 t에 대해 dfs(t)후의 allback[t]값의 합

 

만약 i->t(∈P)가 backedge면 그 수만큼 dfs(i)에서 allback[i]가 증가한 상태이다.

 

/*

위의 본문과 코드를 비교하려면 here=i, next=t 로 바꿔서 읽으면 편할 것이다.

main의 ch부분은 마찬가지로 t로 바꾸면 편하다.

*/

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;
 
//출처: https://blog.myungwoo.kr/116
int N,M;
vector<int> adj[300001];
vector<int> child[300001];
int discovered[300001];
int cnt=1;
int inback[300001];
int parentback[300001];
int allback[300001];
 
 
void dfs(int here,int prev){
    if(discovered[here]==0) discovered[here]=cnt++;
    for(int next:adj[here]){
        if(next!=prev){
            //tree edge
            if(discovered[next]==0){
                child[here].push_back(next);
                int tmp=inback[here];
                dfs(next,here);
               parentback[next]=inback[here]-tmp;
                inback[here]+=inback[next];
                allback[here]+=allback[next];
            }
            //back edge
            else if(discovered[here]>discovered[next]){
                inback[next]++;
                allback[here]++;
            }
        }
    }
}
 
int main(){
    cin>>N>>M;
    for(int i=0;i<M;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,0);
    long long ans=0;
    for(int i=1;i<=N;i++){
        int judge=0;
        for(int ch:child[i]){
            if(inback[ch]>0) judge=1;
            if(allback[ch]-parentback[ch]-inback[ch]>1) judge=1;
        }
        if(judge || M-(N-1)-allback[i] >0) continue;
        ans+=i;
    }
    cout<<ans;
    return 0;
}