[백준 15685번] 드래곤 커브 (시뮬레이션)

본 포스팅의 문제 유형은 삼성 SW 역량테스트 기출문제 중 시뮬레이션 유형입니다. 백준 15685번 드래곤 커브 문제는 stack를 사용하여 방향을 저장하는 것이 핵심이었습니다. 단순한 문제이지만 접근 방식을 떠올리지 못했던 사람들에게는 매우 어려웠던 문제로 기억합니다.

 

2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 14503번] 로봇 청소기 (시뮬레이션)

2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 15685번] 드래곤 커브 (시뮬레이션)

2021.04.17 - [알고리즘/SW역량테스트 기출문제] - [백준 14891번] 톱니바퀴 (시뮬레이션)

 

안녕하세요. 지칸입니다.

오늘 포스팅할 문제는 백준 15685번 드래곤 커브 문제입니다. 직접 시험장에서 풀었던 기억이 있는 문제인데 기억이 새록새록 떠오릅니다. 

 

1) 문제 이해

2) 구조 잡기

3) STL을 사용한 문제 풀이

 

저의 결론) 풀이를 보면 알겠지만 매우 단순한 시물레이션 문제입니다. 다만, 문제 해석을 잘못하면 풀이에 많은 시간이 걸릴 수 있습니다.

---

1) 문제 이해

문제 출처 : www.acmicpc.net/problem/15685

 

문제)

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1) 세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100 × 100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

(그림은 생략했습니다. 문제 출처에 가서 확인 바랍니다..)

 

-> 문제 해석

• 4가지 방향 존재
• 세대가 지나면서 화살표의 방향이 반시계 90 도로 회전됨
• 시작점부터 마지막 지점까지의 화살표 모음 저장
• 화살표 모음의 최근 것부터 맨 처음까지 반시계 90 도로 회전한 화살표를 추가로 저장
• 맵의 크기 101 x 101
• 사각형의 네 꼭짓점 좌표 체크하기

입력)

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

-> 입력 해석

• 드래곤커브 생성을 최대 20번 반복
• 최대 10세대까지 가능, 화살표 2^10개 까지 생성 가능함
• 화살표 방향 정해짐
• x, y순으로 제공됨, map [y][x] 주의

출력)

첫째 줄에 크기가 1 ×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

 

-> 출력 해석

• 전체 맵을 검색 하여 네 꼭짓점 여부 체크 -> 이중 for문

---

2) 구조 잡기

문제 풀기 전에 기본 세팅은 해주는 것이 편합니다.

2019.04.25 - [알고리즘/SW역량테스트] - (1장-1) 역량 테스트 기본 템플릿 준비

 

2-1) 초기 세팅

input을 받을 수 있는 코드를 구현합니다. 여태까지의 풀이와 달리 모든 input을 받아와서 풀이를 진행하지 않고 매 드래곤 커브마다 풀이하도록 코드를 구성해봤습니다. 방식은 어떤 걸로 해도 자유이니 큰 상관없습니다.

#include <iostream>
#include <stack>
using namespace std;
#define MAXMAP 101
int map[MAXMAP][MAXMAP] = { 0, };

int main(void)
{
	int curbCount;
	int direction, generation;
	int result;	
	int startX, startY;
	cin >> curbCount;

	for (int i = 0; i < curbCount; i++)
	{		
		cin >> startX >> startY >> direction >> generation;		   		
		// 드래곤커브 생성하기
	}  
	// 전체 커브 생성 후 네 꼭짓점 찾기
	cout << result;
	return 0;
}

위 코드에서 보이는 것처럼 curbCount 반복문을 돌면서 바로바로 드래곤커브를 생성합니다.

 

2-2) 드래곤커브 만들기

방향 0,1,2,3은 Right, Up, Left, Down순으로 넘버링이 되어 있습니다. 이 순서가 문제의 힌트 역할을 하기도 합니다. 문제 해석에서 처럼 우리는 반시계 90 도로 돌려야 할 필요가 있습니다. 우리는 단순히 1 증가시켜서 그 방향을 도출할 수 있습니다. modifyDir 함수를 보면 input dir에 대해 1 증가시켜 (Down일 경우 다시 Right로) 리턴하고 있습니다.

enum dirName {
	RIGHT, UP, LEFT, DOWN, MaxDIR
};

dirName modifyDir(dirName dir)
{
	int a = (int)dir;
	a++;
	a %= MaxDIR;
	return (dirName)a;	
}

stack<dirName> gen_create(dirName dir, int gen)
{
	stack<dirName> dirarr;
	stack<dirName> copyarr;
	
	dirarr.push(dir);  //0 세대		
	for (int i = 1; i <= gen; i++) //1세대 부터 gen까지
	{
		copyarr = dirarr;
		while (!copyarr.empty()) {
			dirarr.push(modifyDir(copyarr.top()));
			copyarr.pop();
		}		
	}
	return dirarr;
}

int main(void)
{
	int curbCount;
	int  direction, generation;
	int result;	
	int startX, startY;
	cin >> curbCount;

	for (int i = 0; i < curbCount; i++)
	{
		stack<dirName> dirarr();
		cin >> startX >> startY >> direction >> generation;		   
		gen_create((dirName)direction, generation); // gen 생성
	}

	result = findSquare();

	cout << result;

	return 0;
}

stack 타입으로 dirarr를 생성했습니다. 이 배열에 방향을 차곡차곡 넣어줄 예정입니다. 맨 처음 0세대를 넣어준 이후 세대만큼 반복을 진행합니다. while문의 과정을 간단히 아래 그림으로 설명해보겠습니다.

드래곤커브 생성과정

위 사진은 2세대를 생성하는 과정을 간단히 설명한 그림입니다. 맨 처음 copyarr 스택에 dirarr를 복사해줍니다. 그리고 copyarr를 계속 pop 하면서 나오는 화살표를 반시계 90도로 회전시켜 dirarr에 push해주는 과정입니다. 반시계90도 회전은 modifyDir 함수를 통해 구현했습니다. 이렇게 copyarr가 빌 때까지 반복해주면 한 세대의 드래곤커브가 끝입니다. 완성된 dirarr를 리턴하면서 gen_create함수를 종료합니다.

 

2-3) 드래곤커브 맵에 그리기

완성된 dirarr와 시작점만 있으면 우리는 드래곤커브를 그릴 수 있습니다. 이 과정을 insertMap 함수로 구현해봤습니다.

void insertMap(stack<dirName> dirarr, int startX, int startY)
{
	int x, y;
	x = startX;
	y = startY;
	//시작점 넣기
	map[y][x] = 1;
	
	// 화살표 순서 뒤집기
	stack<dirName> reversearr;
	dirName temp;
	int dy[4] = { 0,-1,0,1 };
	int dx[4] = { 1,0,-1,0 };
	while (!dirarr.empty())
	{
		temp = dirarr.top();
		dirarr.pop();
		reversearr.push(temp);
	}
	// 방향에 맞게 넣기
	dirName dir;
	while (!reversearr.empty()) {
		dir = reversearr.top();
		reversearr.pop();
		x += dx[(int)dir];
		y += dy[(int)dir];
		map[y][x] = 1;
	}	
}

int main(void)
{
	//.. 기존코드 생략

	for (int i = 0; i < curbCount; i++)
	{
		stack<dirName> dirarr();
		cin >> startX >> startY >> direction >> generation;		   
		insertMap(gen_create((dirName)direction, generation), startX, startY); // gen 생성
	}

	//.. 기존코드 생략

	return 0;
}

함수 내부를 살펴보면 먼저 시작점 map [y][x] 좌표에 표시를 해줍니다. 그리고 dirarr는 stack 구조이기 때문에 top으로 위에서부터 가져와야 합니다. 화살표 순서는 아래에서 위로 올라가야 하기 때문에 dirarr를 한번 뒤집어 줍니다. reversearr에 뒤집힌 화살표를 넣어줍니다. 간단한 while문으로 구현할 수가 있습니다.

 

이후 시작점부터 하나씩 pop 하면서 방향에 맞게 좌표를 이동시켜 줍니다. 2차원에서 자주 사용하던 dy, dx 배열을 사용하여 우리는 손쉽게 방향에 맞는 좌표로 이동 가능하고 해당 map [y][x]에 표시를 하면서 reversearr가 빌 때까지 반복하면 됩니다. 이 함수를 통해 우리는 하나의 드래곤커브의 꼭짓점들을 맵에 표기할 수 있습니다.

 

2-4) 네 꼭짓점 찾기

모든 드래곤커브를 그린 후 네 꼭짓점을 확인하는 과정을 구현하면 됩니다. 단순히 맵을 전체 탐색하면서 본인 좌표 기준으로 (i, j), (i+1, j), (i, j+1), (i+1, j+1) 네 좌표를 확인하여 하나씩 찾을 수 있습니다.

int findSquare()
{	
	int cnt = 0;
	for (int i = 0; i < MAXMAP; i++)
	{
		for (int j = 0; j < MAXMAP; j++)
		{
			if (map[i][j] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j + 1] == 1)
			{
				cnt++;
			}
		}
	}
	return cnt;
}

int main(void)
{
	//..기존코드 생략
	result = findSquare();
	cout << result;
	return 0;
}