BAEKJOON 9008번: Castle

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

9008번: Castle

사용 알고리즘

깊이 우선 탐색

정렬

 

풀이

문제의 "the interior angle formed by its two incident edges is either 90° or 270°"라는 구절에서 알 수 있듯이 점들을 이은 선들은 무조건 90° or 270°의 각을 만들어야 한다.

따라서 다음과 같은 조건이 성립한다.

 

(x좌표가 같은 점들은 짝수, y좌표가 같은 점들 또한 짝수)

 

따라서 이를 먼저 확인해 주고 먼저 나온 순서대로 x좌표가 같은 점들과 y좌표가 같은 점들을 두 개씩 묶어서 이어준다.

 

이후 겹치는 선이 있는지 확인해 주고, DFS를 통해 처음 정점에서 다른 모든 점들을 탐색하고 다시 원래 점으로 돌아올 수 있는지 확인해준다. 돌아올 수 없거나, 겹치는 선이 있다면 simple rectilinear polygon 이 아니다.

 

마지막까지 모든 과정을 통과했다면 simple rectilinear polygon이며, Yes를 출력하면 된다.

아래는 예시 코드 이다.

#include <bits/stdc++.h>
using namespace std;
struct co{
    int x,y,z,w;
}A[10003];
inline bool cmp(co a,co b){
    return a.x<b.x||(a.x==b.x&&a.y>b.y);
}
vector<set<int> >vsi;
vector<bool>V;
vector<co>L;
int T,n;bool ans,ret;
bool g(int a,int b,int c,int d){
    if(b==1)return false;
    for(int i=0;i<=L.size();i++){
        if(L[i].z==2)continue;
        if(c>d)swap(c,d);
        if(L[i].x<a&&a<L[i].y&&c<L[i].w&&L[i].w<d){
            return true;
        }
    }
    return false;
}
void f(int a){
    for(int i=1;i<=n;i++){
        int j=i+1,cnt=1;
        while(A[i].x==A[j].x&&i<n){
            cnt++;
            if(cnt%2==0){
                vsi[A[i].z].insert(A[j].z);
                vsi[A[j].z].insert(A[i].z);
                co IN;IN.x=A[i].y,IN.y=A[j].y,IN.z=a,IN.w=A[i].x;
                if(IN.x>IN.y)swap(IN.x,IN.y);
                L.push_back(IN);
                if(g(A[i].x,a,A[i].y,A[j].y))ans=false;
            }
            i++;j=i+1;
        }
        if(cnt%2)ans=false;
    }
}
void dfs(int i,int anc){
    set<int>::iterator it;
    for(it=vsi[i].begin();it!=vsi[i].end();it++){
        if(*it!=anc&&*it==1)ret=true;
        if(V[*it])continue;V[*it]=true;
        dfs(*it,i);
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);ans=true;ret=false;
        for(int i=1;i<=n;i++){scanf("%d%d",&A[i].x,&A[i].y);A[i].z=i;}
        sort(A+1,A+1+n,cmp);
        vsi.clear();V.clear(),L.clear();
        vsi.resize(n+1);V.resize(n+1);
        f(1);
        for(int i=1;i<=n;i++)swap(A[i].x,A[i].y);
        sort(A+1,A+1+n,cmp);
        f(2);
        if(!ans){
            printf("NO\n");
            continue;
        }
        V[1]=true;
        dfs(1,0);
        for(int i=1;i<=n;i++)if(!V[i])ret=false;
        if(ret&&ans)printf("YES\n");else printf("NO\n");
    }
    return 0;
}