[백준 15685번 C/C++] 드래곤 커브

 

[백준 15685번 C/C++] 드래곤 커브

 

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

---

 

 

해결전략

 

구현

 

처음 시도할 때, 그려지는 모든 좌표를 기록한 후 재귀를 돌려 90도 회전시켰다. 좋지 않은 방법이고 재귀이기 때문에 시간초과가 나온다. 

 

 

핵심 아이디어

• vector<int> dots;
• 꼭지점의 좌표가 아닌 방향을 저장한다
  • 생성되는 꼭지점을 dots 배열에 담는다. 이 때, 배열의 값은 방향이다.
  • 배열의 값(=방향)을 회전시킬 때 업데이트한다.

---

 

 

정답 코드

 

#include <iostream>
#include <vector>
using namespace std;
 
int dirY[4] = { 0, -1, 0, 1 };
int dirX[4] = { 1, 0, -1, 0 };
 
int n; // 커브의 개수
vector<vector<int>> v(101, vector<int>(101));
 
int CountSquare()
{
	int answer = 0;
	for (int y = 0; y < 100; y++){
		for (int x = 0; x < 100; x++) {
			if (v[y][x] == 1 && v[y][x+1] == 1 && v[y+1][x] == 1 && v[y+1][x+1] == 1){
				answer++;
			}
		}
	}
	return answer;
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n;
	for (int i = 0; i < n; i++){
		int x, y, d, g;
		cin >> x >> y >> d >> g;
 
		// 세대별 방향 계산
		vector<int> dots;
		dots.push_back(d); // 최초의 방향 추가
		for (int j = 0; j < g; j++)
		{
			int size = dots.size();
			for (int k = size - 1; k >= 0; k--){
				dots.push_back((dots[k] + 1) % 4);
			}
		}
 
		// 점 찍기
		v[y][x] = 1; // 시작점
		for (int j = 0; j < dots.size(); j++){
			y += dirY[dots[j]]; // y를 업데이트
			x += dirX[dots[j]]; // x를 업데이트
 
			v[y][x] = 1; // 업데이트된 위치에 점을 찍음
		}
	}
 
	cout << CountSquare();
 
	return 0;
}

 

 

---

 

 

헷깔린 부분

 

처음 시도했다 틀린코드

• ny와 nx라는 새로운 변수를 사용하여 다음 점의 위치를 계산한 후, 이를 바로 v[ny][nx] = 1;에 사용한다.
• 이 방법에서는 x와 y의 값을 업데이트하지 않기 때문에 모든 점이 시작점을 기준으로만 그려지며, 이는 드래곤 커브의 정의와 맞지 않다.
• 따라서 드래곤 커브가 연속적으로 그려지지 않고, 잘못된 위치에 점이 찍히게 된다.

    v[y][x] = 1; // 시작점
    for (int j = 0; j < dots.size(); j++){
        int ny = y + dirY[dots[j]];
        int nx = x + dirX[dots[j]];
 
        v[ny][nx] = 1;
    }

 

 

정답 코드

• 드래곤 커브를 그릴 때 x와 y 변수를 직접 업데이트하여 다음 점을 찍는다.
• 드래곤 커브의 연속성을 유지하는 올바른 방법이다.
• 각 세대의 커브가 이전 세대의 마지막 점에서 올바르게 시작하여 연속적으로 그려진다.

    v[y][x] = 1; // 시작점
    for (int j = 0; j < dots.size(); j++){
        y += dirY[dots[j]];
        x += dirX[dots[j]];
 
        v[y][x] = 1;
    }

 

 

 

정확한 드래곤 커브를 그리기 위해서는 각 점을 찍은 후에 x와 y의 값을 계속해서 업데이트해야 한다. 

그렇지 않으면 모든 점이 첫 번째 점을 기준으로만 그려지게 되어, 드래곤 커브가 아닌 다른 형태가 그려지게 된다. 

---

 

 

 

해설

 

https://www.youtube.com/watch?v=Z2adRzVIPdY&t=8s

 

---