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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17370번 문제인 육각형 우리 속의 개미이다.

문제는 아래 링크를 확인하자.

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

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

개미가 현재 있는 좌표를 (x,y)라고 하자. 처음 개미가 움직인 방향을 "위 방향"으로 볼 때, 개미가 있는 칸에 따라 가능한 다음 개미의 움직임은 위, 아래, 왼쪽, 오른쪽 중 하나로 항상 생각할 수 있다.

또한, 개미가 움직인 횟수의 홀짝에 따라 위로 움직일 수 있는지 아래로 움직일 수 있는지가 달라진다고 생각할 수 있다. 이를 이용하여 완전탐색을 이용하면 문제를 간단히 해결할 수 있다.

 

배열의 인덱스를 음수로 적어넣는 것이 불편하므로, 원점을 적당히 큰 x와 y좌표로 잡아 구현하자. 

 

매 움직임마다 개미는 기존에 온 방향을 제외한 두 방향으로만 새롭게 나아갈 수 있으므로 탐색해야할 경우의 수는 많아야 2^22 일 것임을 알 수 있다. 이는 제한 시간 내에 탐색하기에 충분한 제한시간이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int K;
int cnt = 0;
int arr[50][50];

void func(int x, int y, int dir, int step) {
	if (arr[x][y]) {
		if (step == K) cnt++;
		return;
	}
	if (step == K) return;

	arr[x][y] = 1;
	if ((x + y) & 1) {
		if (dir!=1) func(x - 1, y, -1, step + 1);
		if (dir != -1) func(x + 1, y, 1, step + 1);
		if (dir != 0) func(x, y + 1, 0, step + 1);
	}
	else {
		if (dir != 1) func(x - 1, y, -1, step + 1);
		if (dir != -1) func(x + 1, y, 1, step + 1);
		if (dir != 0) func(x, y - 1, 0, step + 1);
	}
	arr[x][y] = 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K;
	arr[25][25] = 1;
	func(25, 24, 0, 0);

	cout << cnt;
}