[ boj : 17370 ] 육각형 우리 속의 개미

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

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

해설 : 

 

이거 절대 간단한 문제가 아닙니다....(적어도 저는요 ㅠㅠ)

일단 육각형,,,이걸 어떻게 표현해 줄까요??? 여기부터 엄청 꼬이더라구요.

 

먼저 n의 범위부터 체크해보면 최대가 22입니다. 그말은 즉슨 대각선 ,가로,세로 최대 22번밖에 못간다는 뜻이니 

'대충' 적당히 큰 범위를 배열로 선언해 줍시다. 왜 배열로 선언하느냐??? 이미 지나왔던 자취인지 아닌지 알기 위해선 '체크'를 해야할텐데 그걸 배열에 표시를 해줍시다.

 

n의 최대가 22이니 우린 대강 '모든 경우의 수'를 다 해볼 수 있을 거라는 '느낌'이 옵니다. 이 느낌을 '확신'으로 만들수 있어야겠죠.

 

그 전에 먼저 육각형을 배열로 표현해 줍시다. 그 후 6방향으로 어떻게 가다가 딱 n번 탐색했을 때 return , n번 탐색하지 않더라도 이미 방문한 칸이었다면 return 절대 시간초과가 될 수 없겠죠.

 

#include<bits/stdc++.h>

using namespace std;

int n,ans;
int dx[] = { -1,-1,1,1,1,-1 }, dy[] = { 0,1,1,0,-1,-1 };
int dir[][2] = {
	{1,5},
	{0,2},
	{1,3},
	{2,4},
	{3,5},
	{0,4}
};
int board[100][100];

void dfs(int x, int y, int cnt, int d);

int main()
{
	cin >> n;
	board[51][50] = 1;
	dfs(50, 50, 0, 0);
	cout << ans;
	return 0;
}
void dfs(int x, int y, int cnt,int d)
{
	if (cnt == n) {
		if (board[x][y])ans++;
		return;
	}
	if (board[x][y])return;
	board[x][y] = 1;
	dfs(x + dx[dir[d][0]], y + dy[dir[d][0]], cnt + 1, dir[d][0]);
	dfs(x + dx[dir[d][1]], y + dy[dir[d][1]], cnt + 1, dir[d][1]);
	board[x][y] = 0;
}