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

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

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

 

 

 

이문제를 처음 본건 UCPC 2019 예선을 참가 했을때였다. 

그때는 개수를 자체를 세어보려고 경우의 수를 찾고 더하는 방법으로 접근을 했었는데, 예외가 너무 많이 나와서 끝까지 풀지 못한 문제였다. 그러다 다시 풀어볼 기회가 와서 열심히 풀어보았다. ㅎㅎ

 

 

이 문제를 풀때의 핵심은 개미의 이동 방향이다.

 

개마가 이동할 수 있는 벡터의 방향

 

 

그림과 같이 개미가 그래프상에서 움직임이 가능하다. 개미의 위치를 좌표로 생각 할것이기 때문에 이동 후에는 개미의 위치를 저장 해야했다. 초반에 저 벡터의 값을 벡터 크기가 1이라고 생각하고 루트값구해서 코드를 짰는데 소수점의 오차때문에 소수점을 많이 잡으면 돌아서 같은 점을 보는것인데도 다르다고 인식을 하거나 적게 잡으면 다른점을 같은 점이라고 인식하는 오류가 자꾸 생겼다. 그래서 대안으로 정수로 생각한것이다.

 

 

저상태에서 생각해야할것은 개미가 이동했을 시 사용한 벡터 인덱스와 그 방향으로 이동한후에 다음 턴에서 갈수있는 벡터 방향이 규칙으로 나온다는 것이다.

<규칙>       

현재 이동 방향	다음턴에 이동할 수 있는 방향
0	1, 5
1	0, 2
2	1, 3
3	2, 4
4	3, 5
5	4, 0

 

이 규칙을 적용해 완탐을 돌려서 지나온 점을 다시 방문했을 때 회전한 횟수가 주어진 N번과 같으면 카운트한다.

 

 

<결과>

 

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<string>
#include<math.h>
#include<map>
//#define PI 3.14159  
//double C30 = cos((double)60*(PI/180));
//double S60 = sin((double)30 * (PI / 180));
using namespace std;
int X[6] = {0,1,1,0,-1,-1};
int Y[6] = {2,1,-1,-2,-1,1};

map<pair<int,int>,int>re;
int N;
int cnt = 0;
void func(pair<int,int>p, int idx, int n) {
	if (re.count({ p.first, p.second }) > 0) {
		if(n==N)cnt++;
		return;
	}
	if (n > N) return;

	re[{ p.first , p.second }] = n;
	func({ p.first + X[(idx + 1) % 6], p.second + Y[(idx + 1) % 6] }, (idx + 1) % 6, n + 1);
	
	func({ p.first + X[(idx +5) % 6], p.second + Y[(idx +5 ) % 6] }, (idx +5 ) % 6, n + 1);
	
	re.erase({ p.first , p.second });
	return;
}


int main(void) {

	scanf("%d", &N);
	re[{0, 0}]=0;

	func({ 0,2 }, 0, 0);
	printf("%d\n", cnt);
	return 0;
}