[삼성SW테스트] 백준 15685번 - 드래곤 커브

삼성 SW테스트 기출 문제이다. (시뮬레이션)

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

15685번: 드래곤 커브

'드래곤 커브'라는 어떤 규칙을 갖는 선분들이 좌표평면상에 존재할 때 1x1크기의 정사각형이 몇 개 드래곤커브 상에 존재하는지를 묻는 문제였다.

 

기존에 x와 y를 생각하던 것과 반대로 되어 있었다는 점, 방향의 규칙성에 대한 탐색과정이 시간을 끄는 주요 요소였다. 첫 번째 좌표와 관련된 사항은 단순히 x와 y 좌표를 기존의 p[x][y] -> p[y][x] 로 바꿔서 접근해도 되겠구나 생각해서 해결했고, 두 번째 사항은 4세대까지 방향을 숫자로 나열해보면서 깨닫게 되었다. 이런 유형의 문제는 수열로 생각했을 때 1항, 2항, 3항, ... 직접 해보면서 규칙을 발견하는 것이 열쇠라는 것을 다시금 깨달았다.

 

아래는 해답 (0ms 소요)

 

#include <iostream>
#include <vector>
 
using namespace std;
int N, x, y, d, g;
bool check[101][101];
 
struct dir{
    int dy, dx;
};
dir direct[4] = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };
 
void falsing(){
    for (int i = 0; i < 101; i++)
        for (int j = 0; j < 101; j++)
            check[i][j] = false;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int answer = 0;
    vector<int> direction;
 
    cin >> N;
    falsing();
 
    for (int i = 0; i < N; i++){
        cin >> x >> y >> d >> g;
        direction.push_back(d); // 0세대 처리.
        int cur_y = y;
        int cur_x = x;
        check[cur_y][cur_x] = true;
        // 1. 방향들 모두 저장
        for (int gen = 1; gen <= g; gen++){
            for (int indir = direction.size() - 1; indir >= 0; indir--){
                direction.push_back((direction[indir] + 1) % 4);
            }
        }
        // 2. 저장한 방향이용해 모든 점들 체크.
        for (int j = 0; j < direction.size(); j++){
            cur_y += direct[direction[j]].dy; // direction을 인덱스에 넣지 않고 j를넣는 실수.
            cur_x += direct[direction[j]].dx;
            if (!check[cur_y][cur_x] && cur_y >= 0 && cur_y <= 100 && cur_x >= 0 && cur_x <= 100) check[cur_y][cur_x] = true;
        }
        direction.clear();
    }
    for (int i = 0; i <= 99; i++){
        for (int j = 0; j <= 99; j++){
            if (check[i][j] && check[i + 1][j] && check[i][j + 1] && check[i + 1][j + 1]) answer++;
        }
    }
    cout << answer << '\n';
    return 0;
}