본문 바로가기

Computer Science&Engineering/코딩테스트

[ 백준 15685 ] 드레곤 커브

# 문제링크

www.acmicpc.net/problem/15685

 

15685번: 드래곤 커브

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커

www.acmicpc.net

처음에 읽고 나서, 어떻게 풀어야 할 지 전혀 감이 안왔던 문제다.. 저거를 어케 저케 돌리지? 요즘에는 어려우면 빨리 검색해서 접근법을 알아보는데, 결국 방향을 90도로 돌릴 때 규칙을 활용해서 푸는 문제였다. 각 뱡향이 있는 선분을 90도로 돌리면 방향이 +1씩 된다. 그리고 해당 방향을 저장해뒀다가 다음번 세대 돌릴 때 최근 추가된거부터 쭉쭉 체크해주면 된다.

90도를 돌린다고 하면, 어떤 선분이든 다 90도 회전이 되는 게 재미있다. 

 

# 제출 코드 

 

#include <cstdio>
#include <vector>
using namespace std;

int N;
struct st {
	int x;
	int y;
	int d;
	int g;
};
st dragon[21];
int dir[] = { 1, 2, 3, 0 }; // 드래곤 커브 현재에서 -> 세대 진화할 때 
bool map[101][101];

int yd[] = { 0, -1, 0, 1 };
int xd[] = { 1, 0, -1, 0 };
int Solve() {
	for (int i = 0; i < N; i++) { // 각 드래곤 커브 처리해주기
		vector<int> v;
		int cx = dragon[i].x;
		int cy = dragon[i].y;
		map[cx][cy] = 1;
		cx = cx + xd[dragon[i].d];
		cy = cy + yd[dragon[i].d];
		map[cx][cy] = 1;

		v.push_back(dragon[i].d); // 시작

		for (int gen = 1; gen <= dragon[i].g; gen++) {
			int size = v.size() - 1;
			for (int s = size; s >= 0 ; s--) {
				int nd = dir[v[s]];
				cx = cx + xd[nd];
				cy = cy + yd[nd];
				map[cx][cy] = 1;
				
				v.push_back(nd);
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1])ans++;
		}
	}
	return ans;
}
void Input() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d %d", &dragon[i].x, &dragon[i].y, &dragon[i].d, &dragon[i].g);
	}
}
int main() {
	//freopen("sample_input.txt", "r", stdin);
	Input();
	printf("%d", Solve());
}
반응형