백준 15685 c++ "드래곤 커브" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 dy,dx 의 Idx변화량을 이용하는 문제이다.

핵심 사고 방식은 (nextIdx+1)%4 회전하는 방식을 왼쪽과 같은 코드로 생각이 날 수 있냐가 관건이다.

 

처음에 무슨 문제인가 쳐다봤을 때 하나하나 차근차근 문제를 읽고 규칙성을 찾은 결과

세대가 변화할 때 최근에 이동한 변화량을 위와 같은 코드로 작성하게 되면 문제를 풀 수 있게 된다.

 

구현 문제이니 만큼 함수명을 써서 역할을 분담하자!!

 

아래는 코드 해설이다.

코드 설명

1. 전역 변수 및 구조체
   • dy, dx: 각각 오른쪽, 위쪽, 왼쪽, 아래쪽 방향을 나타내는 배열입니다.
   • ddy, ddx: 또 다른 방향 배열로, 같은 순서로 오른쪽, 위쪽, 왼쪽, 아래쪽을 나타냅니다.
   • struct inputData: 시작 좌표 (x, y), 방향 (d), 세대 (g) 정보를 저장하는 구조체입니다

 

• arr: 101x101 크기의 2차원 벡터로, 초기에는 0으로 채워진 격자입니다. 곡선이 지나간 점들을 기록합니다.
• input: 곡선 정보(x, y, d, g)를 저장하는 inputData 구조체의 벡터입니다.
• vecStack: 곡선의 세그먼트 방향을 저장하는 벡터입니다.

---

1. 함수 설명
   • Input()
     • 사용자로부터 곡선의 개수 N을 입력받습니다.
     • arr 격자를 101x101 크기로 초기화하고, 모든 값을 0으로 설정합니다.
     • 각 곡선의 시작 좌표(x, y), 방향(d), 세대(g)를 입력받아 input 벡터에 저장합니다.
   • getInputData()
     • input 벡터에서 특정 곡선(인덱스 i)의 데이터를 가져옵니다.
     • 좌표 x, y, 방향 d, 세대 g를 반환합니다.
   • levelDrawing()
     • 시작 좌표(startSero, startGaro)를 받아 곡선의 다음 세대를 그립니다.
     • vecStack에 저장된 방향을 사용해 새로운 곡선 세그먼트를 생성하고, 격자 arr에 해당 점들을 표시합니다.
     • vecStack에 저장된 모든 세그먼트가 처리될 때까지 그리기를 계속합니다.
   • startDrawing()
     • 주어진 방향 d에 따라 초기 곡선을 그립니다.
     • dy와 dx 배열을 사용해 좌표를 갱신하고, 격자 arr에 점을 표시합니다.
     • 초기 방향을 vecStack에 저장한 후, levelDrawing()을 호출해 다음 세대를 그립니다.
   • Print()
     • 7x7 크기의 격자를 출력하여 현재 상태를 확인합니다. 디버깅 또는 시각화를 위한 함수입니다.
   • getRectangleCount()
     • 격자에서 닫힌 사각형의 개수를 셉니다.
     • 격자의 모든 점을 순회하며, 사방의 네 점이 모두 곡선의 일부인지 확인합니다.
     • 모든 방향에 점이 있으면 사각형 개수를 증가시킵니다.
   • GameStart()
     • 각 곡선에 대해 vecStack을 초기화합니다.
     • getInputData()로 데이터를 가져와 startDrawing()으로 곡선을 생성합니다.
     • getRectangleCount()를 호출해 닫힌 사각형의 개수를 세고, 그 결과를 출력합니다.

---

실행 흐름

1. 입력 처리: Input() 함수가 곡선 개수와 정보를 입력받고 필요한 데이터 구조를 초기화합니다.
2. 곡선 생성: GameStart()가 각 곡선을 반복하며 startDrawing()과 levelDrawing()으로 곡선을 그립니다.
3. 사각형 개수 세기: getRectangleCount() 함수가 격자를 순회하며 닫힌 사각형의 개수를 계산합니다.
4. 출력: 최종적으로 닫힌 사각형의 개수를 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include<stack>

using namespace std;
int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };

int ddy[4] = { 0,1,0,-1 };
int ddx[4] = { 1,0,-1,0 };



typedef struct inputData {
	int x, y, d, g;
}inputData;

int N;
vector<vector<int>> arr;
vector<inputData> input;
vector<int> vecStack;


void Input() {
	cin >> N;
	arr.resize(101);
	for (int i = 0; i < 101; i++) {
		arr[i].resize(101, 0);
	}
	input.resize(N);
	for (int i = 0; i < N; i++) {
		int x, y, d, g;
		cin >> y >> x >> d >> g;
		input[i] = { x,y,d,g };
	}
	

}

void getInputData(int& x, int& y, int& d, int& g , int i) {
	x = input[i].x;
	y = input[i].y;
	d = input[i].d;
	g = input[i].g;
}


void levelDrawing(int &startSero, int &startGaro) {

	int nextSero = startSero;
	int nextGaro = startGaro;
	arr[nextSero][nextGaro] = 1;
	int vecStackSize = vecStack.size();
	for (int i = vecStackSize - 1; i >= 0; i--) {
		int nextD = (vecStack[i] + 1) % 4;
		nextSero = nextSero + dy[nextD];
		nextGaro = nextGaro + dx[nextD];

		arr[nextSero][nextGaro] = 1;
		vecStack.push_back(nextD);

	}
	startSero = nextSero;
	startGaro = nextGaro;
	
	
}

void startDrawing(int sero,int garo,int d,int g) {

	int nextSero = sero;
	int nextGaro = garo;
	for (int i = 0; i <= g; i++) {
		if (i == 0) {
			 nextSero = sero + dy[d];
			 nextGaro = garo + dx[d];
			arr[sero][garo] = 1;
			arr[nextSero][nextGaro] = 1;
			vecStack.push_back(d);
		}
		else {
			//스택에 넣기
			levelDrawing(nextSero,nextGaro);
		}
	}	
}

void Print() {
	for (int i = 0; i < 7; i++) {
		for (int k = 0; k < 7; k++) {
			cout << arr[i][k] << " ";
		}
		cout << '\n';
	}
}

int getRectangleCount() {
	int count = 0;
	for (int i = 0; i < 100; i++) {
		for (int k = 0; k < 100; k++) {
			int nowSero = i;
			int nowGaro = k;
			if (arr[nowSero][nowGaro] == 0)continue;
			int nextSero = nowSero;
			int nextGaro = nowGaro;
			for (int t = 0; t < 4; t++) {
				 nextSero = nextSero + ddy[t];
				 nextGaro = nextGaro + ddx[t];
				if (arr[nextSero][nextGaro] == 0)break;
				if (t == 3) {
				
					count++;
				}
			}
		}
	}
	return count;
}

void GameStart() {
	vector<int> vecStackInit;
	for (int i = 0; i < N; i++) {
		vecStack = vecStackInit;
		int x, y, d, g;
		getInputData(x, y, d, g, i);
		startDrawing(x, y, d, g);
	
	}

	int resultCount = getRectangleCount();
	cout << resultCount;
}

int main(void) {
	Input();
	GameStart();
}