[백준/BOJ] 백준 17370번 : 육각형 우리 속의 개미

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

17370번: 육각형 우리 속의 개미

시작 지점의 좌표가 (500, 500)인 위치에서 시작하는 좌표로 만들었다. 또한 위치마다 {왼쪽 위, 오른쪽 위, 아래}로 갈 수 있는 위치와 {위, 왼쪽 아래, 오른쪽 아래}로 갈 수 있는 위치로 나누어졌다는 것을 고려하였고, 직전 위치로 이동하지 않기 위해 직전에 어디서 왔는지도 고려했다. 방문한 위치에 왔을때 회전을 n번 했는지 확인하고, 방문하지 않은 위치인데 회전을 n번 했는지를 확인하여 문제를 해결했다.

 

코드

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

int n;
vector<vector<int>> visited(1000, vector<int>(1000, 0));
int dxdy[2][3][2] = { {{-1,-1},{-1,1},{1,0}}, {{-1,0},{1,-1},{1,1}} }; //{왼쪽위, 오른쪽위, 아래}로 갈수있는 위치와 {위, 왼쪽아래, 오른쪽아래}로 갈수있는 위치에 따라 나누었다

//before:이전에 있었던 위치
//here:현재 위치
//point:정육각형에서 어느 방향으로 갈 수 있는 위치인지 dxdy[point][][]
//cnt:지금까지 회전한 횟수
int Solve(pair<int, int> before, pair<int, int> here, int point, int cnt)
{
	//방문한 위치일때
	if (visited[here.first][here.second] == 1)
	{
		//회전을 n번 했다면
		if (cnt == n)
			return 1;

		else
			return 0;
	}

	//방문하지 않은 위치인데 회전을 n했다면
	if (cnt == n)
		return 0;

	visited[here.first][here.second] = 1;

	int ret = 0;

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

		//이동해온 위치일때
		if (there == before)
			continue;

		if (point == 0)
			ret += Solve(here, there, 1, cnt + 1);
		else
			ret += Solve(here, there, 0, cnt + 1);
	}

	visited[here.first][here.second] = 0;

	return ret;
}

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

	cin >> n;

	//시작지점
	pair<int, int> start = make_pair(500, 500);
	visited[500][500] = 1;

	pair<int, int> here = make_pair(499, 500); //첫번째 이동방향이 북쪽으로 하므로

	cout << Solve(start, here, 0, 0);

	return 0;
}