[백준/BOJ] 백준 3678번 : 카탄의 개척자

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

3678번: 카탄의 개척자

게임판을 좌표로 만들었다. 움직이는 방향 6개(int dxdy[6][2])를 만들었고, 움직이려는 자리가 비어있지 않을 때 이전에 이동했던 방향으로 또 이동하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int tc;
vector<vector<int>> board(3000, vector<int>(3000, 0));
int dxdy[6][2] = { {-1,-1},{1,-1},{2,0},{1,1},{-1,1},{-2,0} };
vector<int> number_cnt(6, 0); //해당 자원이 몇개 쓰였는지 센다

vector<int> result(10001, 0);

//here과 인접한곳을 확인하고 here에 들어갈 적절한 수를 찾는다
int Check(pair<int, int> here)
{
	vector<int> number_check(6, 0);

	for (int i = 0; i < 6; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		//there이 인접한 자원일때
		if (board[there.first][there.second] != 0)
		{
			number_check[board[there.first][there.second]] = 1;
		}
	}

	int ret = -1;
	int ret_cnt = 987654321;

	//인접하지 않은 자원들중 가장 적게 쓰인 자원을 찾는다
	for (int i = 1; i <= 5; i++)
	{
		//자원i가 인접한곳에서 쓰이지 않았을때
		if (number_check[i] == 0)
		{
			//해당 자원이 적게 나타난 자원일때
			if (ret_cnt > number_cnt[i])
			{
				ret = i;
				ret_cnt = number_cnt[i];
			}
		}
	}

	return ret;
}

void Solve()
{
	pair<int, int> here = make_pair(1500, 1500);
	int here_number = 1;
	int dir = 4;
	int before_dir;

	board[here.first][here.second] = here_number;
	result[1] = here_number;
	number_cnt[1]++;

	here = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);
	dir = 0;

	//i번쨰 타일에 어떤수가 들어있는지 확인
	for (int i = 2; i <= 10000; i++)
	{
		here_number = Check(here);

		board[here.first][here.second] = here_number;
		result[i] = here_number;
		number_cnt[here_number]++;

		pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

		//there위치가 비어 있을때
		if (board[there.first][there.second] == 0)
		{
			here = there; //다음 위치는 해당 위치가 된다

			before_dir = dir; //이전에 어떤 방향으로 이동했는지 저장해 놓는다

			dir++;
			if (dir == 6)
				dir = 0;
		}

		//there위치가 비어있지 않을때 -> 이전에 이동했던 방향으로 또 이동한다
		else
		{
			there = make_pair(here.first + dxdy[before_dir][0], here.second + dxdy[before_dir][1]);

			here = there;
		}
	}
}

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

	Solve();

	cin >> tc;

	for (int i = 0; i < tc; i++)
	{
		int n;
		cin >> n;

		cout << result[n] << "\n";
	}

	return 0;
}