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

 

백준 온라인 저지(BOJ) 3678번 카탄의 개척자

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

3678번: 카탄의 개척자

* 사용언어 : C언어, C++

 

1. 문제

육각형 타일로 이루어진 게임판에 1부터 5까지의 숫자를 한 칸 씩 배치

새로운 타일에는 인접한 타일과 같은 숫자를 배치할 수 없음

① 보드에 가장 적게 배치된 숫자, ② 작은 숫자 순으로 선택

n 번째 타일의 숫자 출력

 

2. 풀이

6각형을 2차원 배열로 표현했고,

이를 활용해 10000번 까지 모두 배치해본 후에 결과를 출력했습니다.

 

1) 2차원 배열 표현

아래와 같이 2차원 배열을 표현하는 규칙을 세웠습니다.

위 예시 그림의 1의 위치를 (y, x) 라고 한다면,

2의 위치는 (y - 1, x + 1), 3의 위치는 (y - 2, x) 입니다.

위 규칙을 dy[], dx[] 배열로 나타냈고,

배열은 (y - 2, x) 로 시작(index 0) 하여 반 시계 방향으로 구현했습니다.

(y - 2, x) 로 시작한 이유는 그리는 규칙을 찾을 때 설명하겠습니다.

 

 

2) 육각형 그리는 규칙

1부터 5까지 숫자를 어떻게 배치할지는 생각하지 않고,

우선 육각형을 어떻게 그려야하는지를 생각해보았습니다.

 

규칙이 전혀 보이지 않아서 우선 손으로 직접 그려보았습니다.

(직접 손으로 그리면서 규칙을 찾았고, 이후에 ppt 로 표현했습니다)

 

위 그림에서 숫자는 타일 배치 순서입니다.

 

(맨 처음 1은 제외)

제일 처음 하늘색 육각형은 방향을 계속 바꾸면서 6개를 배치합니다.

 

두 번째 분홍색 육각형은 8 에서 9 로 1개 배치 후 방향을 바꾸고

이후 2개 씩 배치한 후에 방향을 바꿉니다.

 

세 번째 보라색 육각형은 20에서 22까지 위로 2개 배치 후 방향을 바꾸고

이후 3개 씩 배치한 후에 방향을 바꿉니다.

 

규칙을 찾았습니다.

N번째 육각형은 최초 위치에서 위로 N - 1개 배치 후 방향을 바꾸고

이후 N개 씩 배치한 후 방향을 바꿉니다.

 

이러한 배치 순서에 따라 dy, dx 배열 내 순서도 결정할 수 있습니다.

 

 

3) 배열 크기 및 시작 위치 결정

문제에서 입력 n 은 1부터 10,000 까지 주어지므로

1만 개의 숫자를 게임판에 배치했을 때의 크기를 가늠해봐야합니다.

 

우선 N번째 육각형을 그리기 위해서는 6 * N 개의 타일이 필요합니다.

(1번 : 6개, 2번 : 12개, 3번 : 18개, ...)

위 그림을 통해 확인할 수 있고 각각 선분의 길이가 N이므로

6N 임을 쉽게 파악할 수 있습니다.

 

그리고 N번째 육각형까지 필요한 모든 타일의 개수는 아래와 같습니다.

위 수식을 만족하는 가장 작은 N 은 58 입니다. (58일 때 10,266)

대략 최대 N = 60으로 하면 1만 개를 충분히 배치하고 남습니다.

 

따라서 map 크기를 240(4배), 120(2배)으로 설정했습니다. (1바퀴 당 y ± 2, x ± 1)

하고 중앙값을 올림하여 120, 60 을 시작점으로 정했습니다.

 

(이 문제는 메모리 제한이 거의 없는 수준이라 아주 크게 잡고 풀어도 됩니다)

 

나머지 문제의 규칙 구현은 아래 코드 참고하시면 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

const int LM = 10005;
int res[LM]; // 배치 결과
int cnt[6]; // map 에 배치된 숫자 별 개수
int m[240][120]; // map
int dy[] = { -2, -1, 1, 2, 1, -1 };
int dx[] = { 0, -1, -1, 0, 1, 1 };

int getNextNum(int y, int x) {
	int avail[6] = { 0, };
	for (int i = 0; i < 6; ++i) {
		avail[m[y + dy[i]][x + dx[i]]] = 1;
	}

	int min = 2000; // 10005 / 6 + a
	int v = 0;
	for (int i = 1; i < 6; ++i) {
		if (avail[i] == 0 && cnt[i] < min) {
			min = cnt[i];
			v = i;
		}
	}
	return v;
}

void makeMap() {
	int y = 120, x = 60, idx = 1;
	m[y][x] = 1;
	cnt[1]++;
	res[idx++] = 1;

	int size = 1;

	while (idx < LM) {
		y += dy[5], x += dx[5]; // 다음 육각형 시작 위치 (오른쪽 위)
		int nextNum = getNextNum(y, x);

		m[y][x] = nextNum;
		cnt[nextNum]++;
		res[idx++] = nextNum;

		for (int i = 0; i < 6; ++i) {
			for (int j = 0; j < size; ++j) {
				if (i == 0 && j == size - 1) continue;
				if (idx >= LM) break;
				y += dy[i], x += dx[i];
				nextNum = getNextNum(y, x);
				m[y][x] = nextNum;
				cnt[nextNum]++;
				res[idx++] = nextNum;
			}
		}
		size++;
	}
}

int main() {
	makeMap();

	int T, n;
	scanf("%d", &T);

	while (T--) {
		scanf("%d", &n);
		printf("%d\n", res[n]);
	}
	return 0;
}