[백준 15685] 드래곤 커브

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

 

삼성 B형에서 나올법한 구현 문제이다.

 

지문이 좀 헷갈려서 아래 첨부된 그림을 보고 이해를 했다.

입력이 x, y로 되있는데 실제 좌표와 배열의 인덱스가 다르므로 arr[y][x]로 접근해야 했다.

d가 0, 1, 2, 3으로 동, 북, 서, 남 순서이다.

예제 몇 개를 보면 규칙이 보이는데 예제 1번의 4 2 1 3을 보면

4 2 1 3
북
서
남 서
남 동 남 서
1
2
3 2
3 0 3 2

전 세대의 이동이 다음 세대 이동의 뒷부분과 일치한다는 것이다.

다른 사람들의 풀이는 이전 이동을 뒤집어서 1씩 더한 값을 이용했는데

나는 이전 이동의 앞 1/2부분은 그대로 넣고 뒤 1/2부분은 2씩 더한 후 mod 4를 해서 다음 이동에 넣어줬다

좌표는 중복되어도 되고, 입력의 결과가 배열의 크기를 벗어나는 부분이 없다는 조건이 있어 추가적인 고려는 하지 않았다.

 

주의할 점은 좌표의 경계가 1 ~ 100이 아닌 0 ~ 100이라는 점이다.

 

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
using namespace std;
int N;
bool arr[101][101];
// 동 북 서 남
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};
int main() {
    FASTIO

    cin >> N;
    for(int i = 0; i < N; i++) {
        int x, y, d, g; cin >> x >> y >> d >> g;
        vector<int> v[g + 1];
        v[0].push_back(d);  // 0세대
        for(int k = 1; k <= g; k++) {    // 이동방향 넣고
            if(k == 1) {
                v[1].push_back((d + 1) % 4);  // 1세대
            } else if(k == 2) {
                v[k].push_back((d + 2) % 4);
                v[k].push_back((d + 1) % 4);
            } else {
                for(int l = 0; l < v[k - 1].size(); l++) {
                    if(l < v[k - 1].size() / 2) {
                        v[k].push_back(v[k - 1][l]);
                    } else {
                        v[k].push_back((v[k - 1][l] + 2) % 4);
                    }
                }
                for(int l = 0; l < v[k - 1].size(); l++) {
                    v[k].push_back(v[k - 1][l]);
                }
            }
        }
        arr[y][x] = true;
        for(int k = 0; k <= g; k++) {
            for(int j : v[k]) {
                y += dy[j];
                x += dx[j];
                arr[y][x] = true;
            }
        }
    }
    int res = 0;
    for(int i = 0; i <= 99; i++) {
        for(int j = 0; j <= 99; j++) {
            if(arr[i][j] && arr[i + 1][j] && arr[i][j + 1] && arr[i + 1][j + 1]) {
                res++;
            }
        }
    }
    cout << res;
}