[BOJ / DFS] 17370 육각형 우리 속의 개미

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

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

 

17370 육각형 우리 속의 개미

알고리즘 : Bitmask / DFS

육각형 필드를 배열에 넣는 방법이 중요한 문제입니다. 육각형 이전 움직임에 따른 다음 움직임을 6*2 배열에 넣어두고 현재 배열의 상태를 최대 길이가 44이므로 (오른쪽 왼쪽으로 22칸씩 진행가능하므로) long long int를 이용한 비트마스크로 현재 방문 상태를 저장합니다. 이를 활용해 풀이 가능합니다.

 

 

 

< CODE >

#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

#define MAX 45

int result = 0;
//0 up 1 up right 2 down right 3 down 4 down left 5 up left
int dy[6][2] = {{-1,-1},{-1,1},{-1,1},{1,1},{-1,1},{-1,1}};
int dx[6][2] = {{-1,1},{0,1},{1,0},{-1,1},{-1,0},{0,-1}};
int dValue[6][2] = {{5,1},{0,2},{1,3},{4,2},{5,3},{0,4}};

long long int h[MAX] = {0,};

int n;

void dfs(int y, int x, int move, int last)
{
	if(move >= n)
		return;
		
	for(int i = 0; i < 2; i++)
	{
		pair<int,int> to = {y + dy[last][i], x + dx[last][i]};
			
		if(h[to.first] & (1 << to.second))
		{
			if(move == n - 1)
				result++;
		}
		else
		{
			long long int back = h[to.first];
			h[to.first] |= (1 << to.second);
			dfs(to.first, to.second, move + 1, dValue[last][i]);
			h[to.first] = back;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	
	h[22] |= (1 << 22);
	h[23] |= (1 << 22);
	
	dfs(22,22,0,0);
	
	cout << result << '\n';
	  
	return 0;
}

시간 : 12ms

 

태그 : #BOJ 17370 #백준 17370