[백준 3678] 카탄의 개척자 (C++)

문제 링크: https://www.acmicpc.net/problem/3678

3678번: 카탄의 개척자

1. 주의할 점

- 6각형 형태를 어떻게 나타낼 것인가

  이 부분에 관해서는 백준의 '주사위 윷놀이' 문제와 비슷하다. 어떤 형태로 맵을 나타낼 것인지 떠올리지 못하면 구현 못한다(내 개인적인 생각)

  주사위 윷놀이 링크: https://www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

- 규칙을 어떻게 찾을 것인가

- 배열의 범위 계산(y가 x의 2배보다 널널하게 있어야한다)

 

[맵을 어떤 형태로 나타내고 어떤 규칙을 이용할 것인가]  

 1) 맵을 어떤 형태로 나타낼 것인가

  2차 배열을 이용할 예정이다.

  중앙의 육각 타일을 중심으로 다음과 같은 형태를 지니도록 한다.

 

                         y-2,x

 

           y-1,x-1                y-1,x+1

 

                          y,x           

 

           y+1,x-1               y+1,x+1

 

                         y+2,x

 

위와 같은 형태를 지니게 할 경우, 왜 y의 범위를 x의 2배 이상 해야하는지 이해할 수 있다.

또한, 맵을 잘 보면 가운데 시작점을 기준으로 길이가 1,2,3,...,N인 정육각형으로 덮인다.

그렇다면, 길이가 N인 정육각형까지 쌓게 되는 타일의 수는 1+ N*(N-1)/2

1+N*(N-1)/2 <= 10000 를 만족하는 N은 대략 60으로 잡으면된다. 따라서 좌우로 N의 길이만큼 넉넉히 잡으면 300

위아래는 좌우의 2배만큼 필요하므로 600으로 잡는다.

 

 2) 어떤 규칙이 있는가

  1번부터 시작해서 다음 타일을 쌓는 방향을 시침의 방향으로 표현하면 다음과 같다

시작                   -> 길이 1인 정육각형 : 1, 11, 7, 6, 5, 1

길이 1인 정육각형 -> 길이 2인 정육각형:  1, 12, 11, 11, 7, 7, 6, 6, 5, 5, 1, 1

길이 2인 정육각형 -> 길이 3인 정육각형:  1, 12, 12, 11, 11, 11, 7, 7, 7, 6, 6, 6, 5, 5, 5, 1, 1, 1

 

자세히 살펴보면 항상 처음은 1로 시작한다.

그 이후에는 길이 N-1인 정육각형 ->길이 N인 정육각형을 기준으로 12가 N-1개, 11 N개, 7 N개, 6 N개, 5 N개, 1 N개

 

2. 구현

- 위에서 설명한것을 바탕으로 배열의 시작점을 SY = 300, SX = 150으로 시작하고 가장 중앙에 1은 두고 시작한다.

- 다음 타일이 놓일 위치 구하기 -> 해당 위치에 어떤 타일이 올 수 있는가(Check 함수) -> 해당 위치에 타일을 놓았다면 해당 위치에 어떤 타일이 있는지 저장하는 Arr 배열과 몇번 째 타일은 어떤 번호인지 저장하는 Number 배열과 마지막으로 지금까지 사용한 숫자별 타일의 갯수 Num배열에 추가된 타일 번호의 Index에 1을 더한다

- 10000까지 구한 이후, 숫자를 입력받아서 바로 출력한다.

 

#include <iostream>
using namespace std;
int arr[601][301];
int number[10001];
int level = 1, sx = 150, sy = 300, cnt = 1;
int dx[6] = { 0,-1,-1,0,1,1 };
int dy[6] = { -2,-1,1,2,1,-1 };
int num[6] = { 0,1,0,0,0,0 };		//사용한 숫자
bool avail[6];

void check() {
	for (int i = 1; i < 6; i++)
		avail[i] = false;
	//인접한것들 true로 전환
	for (int i = 0; i < 6; i++) {
		int nx = sx + dx[i];
		int ny = sy + dy[i];
		int val = arr[ny][nx];
		if (val != 0) avail[val] = true;
	}
	int maxi = 10000;
	int idx = 0;
	for (int i = 1; i < 6; i++) {
		if (!avail[i]) {				//인접하지 않으면서
			if (num[i] < maxi) {		//사용한 갯수가 가장 적으면서, i값이 작은거
				maxi = num[i];
				idx = i;
			}
		}
	}
	arr[sy][sx] = idx;
	num[idx]++;
	number[++cnt] = idx;
}

void cal() {
	while (level < 61) {
		sx += 1;
		sy -= 1;
		check();
		if (cnt == 10001) break;
		for (int i = 0; i < level - 1; i++) {
			sx += dx[0];
			sy += dy[0];
			check();
			if (cnt == 10001) break;
		}
		for (int k = 1; k <= 5; k++) {
			for (int i = 0; i < level; i++) {
				sx += dx[k];
				sy += dy[k];
				check();
				if (cnt == 10001) break;
			}
		}
		level++;
	}
}

int main() {
	int test, target;
	cin >> test;
	arr[sy][sx] = 1;
	number[1] = 1;
	cal();
	for (int t = 0; t < test; t++) {
		cin >> target;
		cout << number[target] << '\n';
	}
	system("pause");
	return 0;
}