[BOJ][백준 15685] 드래곤 커브 - C++

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

15685번: 드래곤 커브

백준 사이트의 15685번 문제, 드래곤 커브 문제다.

이름이 굉장히 멋들어지길래 골랐다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

드래곤 커브의 규칙

• K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.
• 크기가 100×100인 격자 위에 드래곤 커브가 N개 있다.
  • 드래곤 커브의 개수 N(1 ≤ N ≤ 20)
• 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다.
  • x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)
• 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 
• 드래곤 커브는 서로 겹칠 수 있다.
• 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오.

---

1. 문제풀이 아이디어

• 드래곤커브의 규칙을 이해하는데 굉장히 애를 먹었다...

고민의 흔적

• 내가 찾은 규칙은 시작방향에 따라 다음과 같이 나뉘어진다.
  • 시작방향이 상or하 => 상&하는 정방향으로, 좌&우는 역방향으로 붙는다. (따라서 좌,우는 빼줘야함)
  • 시작방향이 좌or우 => 좌&우는 정방향으로, 상&하는 역방향으로 붙는다. (따라서 상,하는 빼줘야함)
• 전체적인 알고리즘 순서는 다음과 같다.
  • 각 커브시작 점에서 재귀적으로 앞으로의 방향을 구해준다. (지금까지의 원소들이 역순으로 90도 회전해서 다음 벡터의 원소로 들어가게 됨)
  • 채운 드래곤커브의 방향 정보로 지도에 1을 채워준다. (규칙은 위에 설명과 같음)
  • 지도를 전부 채우면 이 지도의 정보로 정사각형의 개수를 구해준다.

---

2. 코드 핵심 부분

1) 각 커브의 목표세대만큼 방향벡터를 구해서 채워주는 함수,

   이 규칙도 처음에 잘못 파악해서 꼬였었다..

   방향벡터 Diry, Dirx를 처음에 우상좌하 순서로 만들어놓았기에 90도 회전하기 편했다.

   지금까지의 벡터들 만큼 다음 세대에 추가되는 것인데, 그게 역순이라는 것이 포인트였다.

// 재귀적으로 세대만큼 방향을 채워주는 함수
void fillDir(int Type, int nowG) {
	// 목표 세대에 도달하면 종료
	if (nowG == Drag[Type][3]) {
		return;
	}

	// 지금까지의 벡터들을 역순으로 90도 회전해서 다음 벡터에 넣어주는 것이다.
	int Size = Dir.size();
	for (int i = Size - 1; i >= 0; i--) {
		Dir.push_back((Dir[i] + 3) % 4);
	}

	fillDir(Type, nowG + 1);
}

 

2) 채운 드래곤커브 정보로 지도에 1을 찍어주는 함수,

   이 함수부분도 규칙을 파악하는데 애를 먹었었다.

   규칙에서 꼭 파악해야 하는 부분 두가지가

      1. 커브가 정방향으로 붙기도 하고, 역방향으로 붙기도 하는데 그걸 알아야 한다.

      2. 시작방향이 상,하냐 좌,우냐에 따라 경우가 나뉜다. (근데 이것은 다른 방식으로 구현하면 신경안써도 될지도)

// 채운 드래곤커브 정보로 지도에 점을 채워줌 (1로)
void fillDot(int Type) {
	int Sy = Drag[Type][0];
	int Sx = Drag[Type][1];
	
	// 시작 점을 채우고 시작
	Map[Sy][Sx] = 1;
	int Size = Dir.size();
	
	// 시작방향이 상하냐 좌우냐에 따라 계산이 달라진다.
	// 시작방향이 상, 하 일때
	if (Dir[0] == 0 || Dir[0] == 2) {
		for (int i = 0; i < Size; i++) {
			if (Dir[i] == 0 || Dir[i] == 2) {
				Sy += Diry[Dir[i]];
				Sx += Dirx[Dir[i]];
				Map[Sy][Sx] = 1;
			}
			else {
				Sy -= Diry[Dir[i]];
				Sx -= Dirx[Dir[i]];
				Map[Sy][Sx] = 1;
			}
		}
	}
	// 시작방향이 좌, 우 일때
	else {
		for (int i = 0; i < Size; i++) {
			if (Dir[i] == 0 || Dir[i] == 2) {
				Sy -= Diry[Dir[i]];
				Sx -= Dirx[Dir[i]];
				Map[Sy][Sx] = 1;
			}
			else {
				Sy += Diry[Dir[i]];
				Sx += Dirx[Dir[i]];
				Map[Sy][Sx] = 1;
			}
		}
	}
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// 필요 인자들
int N; // 드래곤 커브의 개수 (1 ≤ N ≤ 20)
int Drag[20][4]; // 각 커브 정보 (y, x, 방향, 세대)
int Map[101][101]; // 지도
vector<int> Dir; // 방향을 저장
int Ans;

// 방향배열 (0: 우, 1: 상, 2: 좌, 3: 하)
int Diry[] = { 0, -1, 0, 1 };
int Dirx[] = { 1, 0, -1, 0 };

// 값 입력받는 함수
void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y, d, g;
		cin >> x >> y >> d >> g;
		Drag[i][0] = y;
		Drag[i][1] = x;
		Drag[i][2] = d;
		Drag[i][3] = g;
	}
}

// 재귀적으로 세대만큼 방향을 채워주는 함수
void fillDir(int Type, int nowG) {
	// 목표 세대에 도달하면 종료
	if (nowG == Drag[Type][3]) {
		return;
	}

	// 지금까지의 벡터들을 역순으로 90도 회전해서 다음 벡터에 넣어주는 것이다.
	int Size = Dir.size();
	for (int i = Size - 1; i >= 0; i--) {
		Dir.push_back((Dir[i] + 3) % 4);
	}

	fillDir(Type, nowG + 1);
}

// 채운 드래곤커브 정보로 지도에 점을 채워줌 (1로)
void fillDot(int Type) {
	int Sy = Drag[Type][0];
	int Sx = Drag[Type][1];
	
	// 시작 점을 채우고 시작
	Map[Sy][Sx] = 1;
	int Size = Dir.size();
	
	// 시작방향이 상하냐 좌우냐에 따라 계산이 달라진다.
	// 시작방향이 상, 하 일때
	if (Dir[0] == 0 || Dir[0] == 2) {
		for (int i = 0; i < Size; i++) {
			if (Dir[i] == 0 || Dir[i] == 2) {
				Sy += Diry[Dir[i]];
				Sx += Dirx[Dir[i]];
				Map[Sy][Sx] = 1;
			}
			else {
				Sy -= Diry[Dir[i]];
				Sx -= Dirx[Dir[i]];
				Map[Sy][Sx] = 1;
			}
		}
	}
	// 시작방향이 좌, 우 일때
	else {
		for (int i = 0; i < Size; i++) {
			if (Dir[i] == 0 || Dir[i] == 2) {
				Sy -= Diry[Dir[i]];
				Sx -= Dirx[Dir[i]];
				Map[Sy][Sx] = 1;
			}
			else {
				Sy += Diry[Dir[i]];
				Sx += Dirx[Dir[i]];
				Map[Sy][Sx] = 1;
			}
		}
	}
}

// 정사각형 체크
int isValid(int Sy, int Sx) {
	if (!Map[Sy + 1][Sx]) return 0;
	if (!Map[Sy + 1][Sx + 1]) return 0;
	if (!Map[Sy][Sx + 1]) return 0;
	return 1;
}

// 네 꼭짓점 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 함수
void calcBox() {
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (Map[i][j] == 1) {
				int ret = isValid(i, j);
				Ans += ret;
			}
		}
	}
}

// 메인함수
int main() {

	// input
	input();

	// solve
	// 재귀적으로 각 드래곤커브별로 나아가며 방향벡터를 채워준다.
	for (int i = 0; i < N; i++) {
		// 초기화
		Dir.clear();
		Dir.resize(0);
		// 시작방향 넣어줌
		Dir.push_back(Drag[i][2]);
		// 방향벡터 채워주는 함수 실행
		fillDir(i, 0);
		// 채운 방향벡터로 지도에 점 표시
		fillDot(i);
	}

	// output
	// 네 꼭짓점 모두 드래곤 커브의 일부인 정사각형의 개수를 구해준다.
	calcBox();
	cout << Ans;

	return 0;
}

---

4. 문제 풀이를 마치며..

백준 채점 결과

처음 문제 이해부터 어지러웠던 문제이다.

내가 워낙 공간지각 능력이나 도형에 약해서 규칙 이해가 쉽지않았다.

 

구현방식 자체는 크게 어려운 부분이 없기 때문에,

문제를 얼마나 잘 이해하느냐에 따라서 개인편차가 크게 있을듯한 문제였다.

 

그리고 이 문제를 품으로서..

백준 실버티어를 달성하게 되었다!

 

나의 승급전 문제였던 것인데,

한번에 풀리지 않고 코드 수정이 여러번 있었던만큼

성공하고 승급하였을때 더욱 성취감이 있었다 야호.