문제

문제 링크

선이 일정한 규칙으로 증가하는데 규칙대로 선을 이어보고 선으로 이루어진 박스를 체크하는 문제다.
결국 요구하는건 주어진 규칙대로 선을 그릴 수 있냐고 묻는 문제다.

지렁이가 각 세대를 증가하면서 길이가 점점 2배가 된다. 그리고 각 움직임에는 방향성이 존재한다.

처음에 접근한 방법은 각 방향을 기록해보고 세대를 증가할때 다시 거슬러 가는 방법이었다.
회전이라는 말때문에 처음에 당황했는데 방향성을 생각해보니 알게되었다.

문제에서 제시한 방향이다.

// 우0 상1 좌2 하3
int dy[]={0,-1,0,1};
int dx[]={1,0,-1,0};

왜 방향을 이렇게 제시했을까 생각하다가 선을 회전할때 인덱스를 1씩 증가하면되는 것을 발견했다. 우를 회전하면 상이 되는데 이는 배열 인덱스+1 이다. 나머지도 동일했다.

그래서 방향성 문제를 해결하고 증가하는 규칙에 집중했다.

예제1에 증가 순서이다.

u,l,d,l
1,2,3,2

d,r,d,l
3,0,3,2

현재 자신의 길이만큼 증가하고 stack처럼 최신 길을 확인하며 방향이 정해졌다.

void _curve(){
    int vecSize=way.size();
    for(int i=vecSize-1;i>=0;i--){
        int newWay=(way[i]+1)%4;
        way.push_back(newWay);
    }
}

핵심적인 부분이 결정되니 나머지는 쉽게 해결할 수 있었다.

또한 마지막에 박스 체크를 할때 0부터 100까지 진행하지않고 y,x에 최소 최대를 구해 정해진 범위까지만 계산하였다.

code

/**
 * 백준 15685
 * 20:52 22:18
*/
#include <bits/stdc++.h>
#define MAX 1e9
using namespace std;

int graph[101][101]={0};
int minY=99,minX=99;
int maxY=0,maxX=0;
vector<int> way;

// 우0 상1 좌2 하3
int dy[]={0,-1,0,1};
int dx[]={1,0,-1,0};

void pointGraph(int y,int x){
    if(y<0 || y>100 || x<0 || x>100) return;
    minY=(minY>y)?y:minY;
    minX=(minX>x)?x:minX;
    maxY=(y>maxY)?y:maxY;
    maxX=(x>maxX)?x:maxX;
    graph[y][x]=1;
}
void _curve(){
    int vecSize=way.size();
    for(int i=vecSize-1;i>=0;i--){
        int newWay=(way[i]+1)%4;
        way.push_back(newWay);
    }
}
void curve(int x,int y,int d,int g){
    way.clear();
    if(g>=0) way.push_back(d);
    for(int i=1;i<=g;i++){
        _curve();
    }
    // way 따라서 graph 표시
    int my=y,mx=x;
    pointGraph(my,mx);
    for(int i=0;i<way.size();i++){
        my+=dy[way[i]];
        mx+=dx[way[i]];
        pointGraph(my,mx);
    }
}
int cntSqure(){
    // minY,minX부터 maxY,maxX까지 중
    // 4개 체크되면 cnt
    int ret=0;
    for(int i=minY;i<maxY;i++){
        for(int j=minX;j<maxX;j++){
            int cnt=0;
            if (graph[i][j]==1) cnt++;
            if (graph[i+1][j]==1) cnt++;
            if (graph[i][j+1]==1) cnt++;
            if (graph[i+1][j+1]==1) cnt++;
            if (cnt==4) ret++;
        }
    }
    return ret;
}
int main(void){
    int N;
    cin>>N;
    int x,y,d,g;
    while(N--){
        cin>>x>>y>>d>>g;
        curve(x,y,d,g);
    }
    // cntSquare
    int ans=cntSqure();
    cout<<ans<<endl;
}