[BOJ 8893] Pandora

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8893 에서 채점할 수 있습니다.

요약 )

 LRLLRLL 형식으로 주어지는 다각형이 y축으로 monotone 인지를 확인하면 해결할 수 있습니다. (x축은 y축과 비슷한 방법으로 해결 가능합니다.) y축으로 monotone이 아니기 위해선 y축 방향으로 오목한 부분이 있어야 합니다. 그래야 y축에 평행한 직선이 다각형을 여러 번 자를 수 있습니다. 다시 말하면 아래와 같은 진행 방향이 나와야만 y축으로 monotone이 아닙니다.

 반시계 방향으로 돌아가기 때문에, y축 monotone에 영향을 끼치는 오목한 부분은 위의 두 가지 경우만이 존재합니다. 다시 말하면 이 두 가지 경우가 모두 없다면 monotone 이고, 둘 중 하나라도 존재한다면 monotone이 아닙니다. 이제 이런 오목한 부분이 있는지 여부를 탐색하는 프로그램을 만들면 문제를 해결할 수 있습니다.

입력 )

// code by RiKang, weeklyps.com
string s;
 
void solve(){
    cin>>s;
    s.push_back(s[0]);
    s.push_back(s[1]);
}

 이 풀이에서는 string으로 입력받은 다음, 출발 지점이 오목한 경우에 대비해 s[0]과 s[1]을 추가시켜 주었습니다. 이 추가를 하지 않으면 출발 지점이 오목한 경우를 따로 예외 처리해줘야 하기 때문에 구현의 편의성을 위해 추가한 것입니다.

현재 방향, 이전 방향, 이전의 이전 방향 기억하기 )

 오목한지를 판별하기 위해선 3개의 방향이 필요합니다. 따라서 현재 방향, 이전 방향, 이전의 이전 방향을 기억할 필요가 있습니다.

// code by RiKang, weeklyps.com
void solve(){
    int ppdir=0, pdir=0, dir=0; // 0 = 위, 1 = 왼, 2 = 아래, 3 = 오른
    for(int i=0; i<s.size(); i++){
        if(s[i]=='L'){
            ppdir=pdir;
            pdir=dir;
            dir=(dir+1)%4;
        }
        else{
            ppdir=pdir;
            pdir=dir;
            dir=(dir+3)%4;
        }
    }
}

 위와 같이 방향을 int형으로 저장하고, 0 = 오른쪽, 1 = 왼쪽, 2 = 아래쪽, 3 = 오른쪽 진행방향이라는 의미를 부여하면 쉽게 회전을 구현할 수 있습니다. 왼쪽으로 회전은 dir=(dir+1)%4, 오른쪽으로 회전은 dir=(dir+3)%4로 가능합니다. 또한 이전 방향과 이전 이전 방향을 기억하기 위해 pdir, ppdir에 그 값을 저장하였습니다.

y축 monotone 판별 )

// code by RiKang, weeklyps.com
void solve(){
    int ppdir=0, pdir=0, dir=0; // 0 = 위, 1 = 왼, 2 = 아래, 3 = 오른
    int y=1; // 단조 = 1, 단조X = 0
    for(int i=0; i<s.size(); i++){
        if(s[i]=='L'){
            ppdir=pdir;
            pdir=dir;
            dir=(dir+1)%4;
        }
        else{
            ppdir=pdir;
            pdir=dir;
            dir=(dir+3)%4;
        }
        if(i<=1) continue;
        if(ppdir==1 && pdir==0 && dir==3) y=0; // 오목!
        if(ppdir==3 && pdir==2 && dir==1) y=0; // 오목!
    }
}

 3개의 진행 방향을 저장했기 때문에 오목한지를 위와 같은 조건문으로 확인할 수 있습니다. 또한 s뒤에 s[0],s[1]을 추가했기 때문에 출발 지점이 오목한 경우의 예외 처리는 하지 않아도 됩니다. x축 판별도 비슷합니다. 이는 아래 최종 코드에서 확인할 수 있습니다.

최종 코드 )

// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - F
// BOJ 8893 Pandora
 
#include <bits/stdc++.h>
using namespace::std;
 
string s;
 
void solve(){
    cin>>s;
    s.push_back(s[0]);
    s.push_back(s[1]);
    int ppdir=0, pdir=0, dir=0; // 0 = 위, 1 = 왼, 2 = 아래, 3 = 오른
    int x=1, y=1; // 단조 = 1, 단조X = 0
    for(int i=0; i<s.size(); i++){
        if(s[i]=='L'){
            ppdir=pdir;
            pdir=dir;
            dir=(dir+1)%4;
        }
        else{
            ppdir=pdir;
            pdir=dir;
            dir=(dir+3)%4;
        }
        if(i<=1) continue;
        if(ppdir==1 && pdir==0 && dir==3) y=0;
        if(ppdir==3 && pdir==2 && dir==1) y=0;
        if(ppdir==0 && pdir==3 && dir==2) x=0;
        if(ppdir==2 && pdir==1 && dir==0) x=0;
    }
    printf("%d\n",x+y);
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}