백준 15685번 드래곤커브 (C++)

문제 링크 : www.acmicpc.net/problem/15685

15685번: 드래곤 커브

이 문제에서 모든 지점의 값들을 매번 하나하나 저장해주고 그에 따른 회전값들을 매 순간 판단한다면 시간효율성이 비효율적일 것이다.

때문에 핵심적으로 회전방향만 저장해줄 것이다.

 

문제 풀이는 다음과 같다.

 

1. 먼저 이 문제의 규칙은 다음과 같다.

드래곤 커브에 대한 설명을 함축하자면, 이전 선분을 시계방향으로 90도 회전한 것을 마지막 지점에 그대로 가져다 붙이면 된다.

 

2. 아래와 같이 변수들을 정의하고 시작지점과 방향, 드래곤커브의 단계를 입력 받는다.

dragon이라는 void함수에 위치값과 회전값, 드래곤커브의 단계를 매개변수로 넣어준다.

    int t,x,y,d,g;
    cin >> t;
    for(int i=0; i<t; i++){
        cin >> x >> y >> d >> g;
        dragon(x,y,d,g);
    }

 

3. 아래는 void타입의 dragon함수이다. 코드의 윤곽만 대충 보고 상세 설명은 다음 단계로 나아가면서 차근히 이해해보자.

void dragon(int x, int y, int d, int g){ // d = 시작 방향
    vector<int> temp;
    temp.push_back(d);
    while(g--){ // 1번 
        for(int i=temp.size()-1; i>=0; i--){
            dir = temp[i]+1;
            if(dir>3) dir = 0;
            temp.push_back(dir);
        }
    }
    ny = y, nx = x;
    ch[ny][nx] = true; // 2번
    for(int i=0; i<temp.size(); i++){
        ny+=my[temp[i]];
        nx+=mx[temp[i]];
        if(ny>100||ny<0||nx>100||nx<0) continue;
        if(!ch[ny][nx]) ch[ny][nx] = true;
    }
}  

 

4. 드래곤 함수를 구하기 위해 만약 좌표값을 일일이 하나하나 저장해서 그에 따른 회전값을 새로 저장해준다면, 코드 효율성 자체가 비효율적이게 나오거나 자칫하면 시간초과가 나올 수 있을 것이다. 때문에 나는 최초의 지점에서부터 회전하는 방향들을 모두 저장하는 방식을 채택했다.

 

예를 들어 위와 같은 드래곤 커브를 봐보자. 숫자는 순서대로 이동하는 방향을 뜻한다.

자세히보면 2번 방향은 반시계 방향으로 90도꺽어서 2 -> 3번으로 방향을 틀었다.

1번 방향도 마찬가지로 반시계 방향으로 90도 꺽어서 1 -> 4번으로 방향을 틀었다.

이를 함축하자면, 누적된 방향의 마지막 값에서부터 반시계 방향으로 90도 꺽은 값이 회전값에 누적된다.

    while(g--){ // 1번 
        for(int i=temp.size()-1; i>=0; i--){
            dir = temp[i]+1;
            if(dir>3) dir = 0;
            temp.push_back(dir);
        }
    }

위의 핵심을 코드로 녹아내면 위와 같이 나온다.

 

5. 이렇게 저장된 값들은 최초의 시작지점을 기준으로 하나하나 회전해나가며 bool문을 체크해주면 된다.

    ny = y, nx = x;
    ch[ny][nx] = true; // 2번
    for(int i=0; i<temp.size(); i++){
        ny+=my[temp[i]];
        nx+=mx[temp[i]];
        if(ny>100||ny<0||nx>100||nx<0) continue;
        if(!ch[ny][nx]) ch[ny][nx] = true;
    }

이때 범위 밖에 해당되는 값은 continue를 해주자

 

6. 모든 값들을 저장해줬으면 이제 정사각형의 네 꼭짓점이 모두 드래곤커브인지를 판단해보자.

판단하는 로직 자체는 한 점을 기준으로 사각형의 포인트만을 체크해주면 되므로, 그리 어렵지 않다.

    for(int i=0; i<MAX-1; i++){
        for(int j=0; j<MAX-1; j++){
            y = i, x = j;
            box = false;
            if(ch[y][x]){
                for(int i=0; i<3; i++){
                    ny = y+by[i];
                    nx = x+bx[i];
                    if(!ch[ny][nx]){
                        box = true;
                        break;
                    }
                }
            }
            else box = true;
            if(!box) ans++;
        }
    }

이때 for문의 체크 범위가 최대 99까지인것을 놓치면 안된다.

 

#include <iostream>
#include <vector>
#define MAX 101
using namespace std;
// 0 : 오른쪽, 1 : 위쪽, 2 : 왼쪽, 3 : 아래쪽
int dir,ny,nx,my[] = {0,-1,0,1},mx[]={1,0,-1,0},by[]={0,1,1},bx[]={1,0,1},ans=0;
bool ch[MAX][MAX], box;

void dragon(int x, int y, int d, int g){ // d = 시작 방향
    vector<int> temp;
    temp.push_back(d);
    while(g--){
        for(int i=temp.size()-1; i>=0; i--){
            dir = temp[i]+1;
            if(dir>3) dir = 0;
            temp.push_back(dir);
        }
    }
    ny = y, nx = x;
    ch[ny][nx] = true;
    for(int i=0; i<temp.size(); i++){
        ny+=my[temp[i]];
        nx+=mx[temp[i]];
        if(ny>100||ny<0||nx>100||nx<0) continue;
        if(!ch[ny][nx]) ch[ny][nx] = true;
    }
}  

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t,x,y,d,g;
    cin >> t;
    for(int i=0; i<t; i++){
        cin >> x >> y >> d >> g;
        dragon(x,y,d,g);
    }
    for(int i=0; i<MAX-1; i++){
        for(int j=0; j<MAX-1; j++){
            y = i, x = j;
            box = false;
            if(ch[y][x]){
                for(int i=0; i<3; i++){
                    ny = y+by[i];
                    nx = x+bx[i];
                    if(!ch[ny][nx]){
                        box = true;
                        break;
                    }
                }
            }
            else box = true;
            if(!box) ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}