백준 3678번 카탄의 개척자 C++

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

 

2차원 배열로 육각형 타일을 직접 구현하였다.

↗↑↖↙↓↘의 패턴이 처음엔 각각 ( 1, 0, 1, 1, 1, 1) 의 횟수만큼 나타나고 1씩 증가한다.

두 번째엔 (2, 1, 2, 2, 2, 2) 만큼, 세 번째엔 (3, 2, 3, 3, 3, 3) ... 이런 식으로 나타난다.

이걸 잘 구현해서 문제를 해결하였다.

n이 50일 때 출력한 모습이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int dRow[6] = { -1,-2,-1,1,2,1 };
int dCol[6] = { 1,0,-1,-1,0,1 };
int moveCnt[6] = { 1,0,1,1,1,1 };
vector<int> tileCnt(6, 0);
vector<int> ans(10001);
vector<vector<int>> board(300, vector<int>(300));

int GetTileNum(int row, int col) {
	vector<bool> isPossibleTile(6, true);
	for (int i = 0; i < 6; i++) {
		isPossibleTile[board[row + dRow[i]][col + dCol[i]]] = false;
	}
	int min_cnt = 10000;
	int tile = -1;
	for (int i = 1; i <= 5; i++) {
		if (!isPossibleTile[i]) continue;
		if (min_cnt > tileCnt[i]) {
			min_cnt = tileCnt[i];
			tile = i;
		}
	}
	return tile;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int row = 150;
	int col = 150;
	board[row][col] = 1;
	ans[1] = 1;
	tileCnt[1]++;
	int dir = 0;
	int cnt = 0;
	for (int i = 2; i <= 10000;) {
		if (cnt == moveCnt[dir]) {
			moveCnt[dir]++;
			dir = (dir + 1) % 6;
			cnt = 0;
			continue;
		}
		row += dRow[dir];
		col += dCol[dir];
		int tileNum = GetTileNum(row, col);
		board[row][col] = tileNum;
		tileCnt[tileNum]++;
		ans[i] = tileNum;
		cnt++;
		i++;
	}
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		cout << ans[n] << "\n";
	}
};