[백준/C++] 17370. 육각형 우리 속의 개미

문제

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

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

무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다.

개미 우리의 모습

곤충 관찰이 취미인 유이는 세 정육각형이 서로 맞닿아 있는 어떤 점 위에 개미를 하나 올렸다. 이렇게 우리에 올라온 개미는 그 자신에게 미지의 영역인 우리를 페로몬을 뿌리며 탐색하기 시작했다. 처음 개미는 점과 연결된 세 변 중 하나를 향해 이동을 시작하는데, 편의를 위해 이 첫 번째 이동이 북쪽을 향하도록 돌려서 보자.

만약 개미가 변이 세 갈래로 갈라지는 점에 도착하면, 자신이 이동해온 변을 제외한 나머지 두 변 중 하나를 골라 그 방향으로 회전하여 탐색을 계속한다.

연두색은 시작 지점, 초록색은 개미가 탐색하며 페로몬을 뿌린 경로. 검은색은 개미, 주황색은 다음 이동을 위해 선택 가능한 두 변을 나타낸다.

개미가 이전에 방문했던, 즉, 페로몬이 뿌려진 지점에 도착하면 이곳이 이미 익숙한 영역이라는 착각에 빠지고 더 이상의 탐색을 멈춘다. 이렇게 탐색을 멈췄을 때, 방향을 회전한 횟수가 정확히 N번이 되는 경우의 수를 구해보자.

방향을 7번 회전하는 두 경로. 페로몬의 궤적은 동일해도 개미의 이동 방향에 따라 경로를 구별하도록 한다.

풀이

DFS를 돌리기 위해

육각형 모양의 맵을, 아래와 같이 2차원 배열에 나타내었다. 

편의를 위해 이 첫 번째 이동이 북쪽을 향하도록 돌려서 보자. 라고 문제에 나와있으므로, 

시작할 때는 직전 이동이 1번이동이라고 생각하고 4번 이동과 2번이동이 가능한 상태로 시작한다. 

(하지만 저 첫번째 이동은 N을 세는 횟수에는 포함되지 않으므로 주의) 

 

아무튼, 육각형을 2차원 배열에 나타내고, 

직전 이동에 따라 다음에 이동이 가능한 경우를 배열로 만들어놓고 사용해서 DFS를 돌렸다. 

 

DFS를 돌리다가 이동횟수가 N인데, 직전에 방문한 위치이면 답을 +1 해주었다. 

 

N의 최댓값이 22이므로, 맵의 크기는 대강 101으로 해주고

(50,50)에서 (49,50)으로 첫번째 이동을 했다고 생각하고 해당 위치에서 DFS를 시작했다. 

코드

#include <iostream>

using namespace std;

int N;
bool visited[101][101];

int answer = 0;

//last =>  0:↑, 1:↓, 2:↗, 3:↙, 4:↖, 5:↘
int route[6][2][2] = { {{-1,-1},{-1,1}}, {{1,-1},{1,1}}, {{-1,0},{1,1}}, {{1,0},{-1,-1}}, {{1,-1},{-1,0}}, {{-1,1},{1,0}} };
int lasts[6][2] = { {4, 2}, {3, 5}, {0, 5}, {1, 4}, {3, 0}, {2, 1} };


void DFS(int r, int c, int count, int last) {

	for (int i = 0;i < 2;i++) {
		int dr = route[last][i][0];
		int dc = route[last][i][1];
		int now = lasts[last][i];

		int nextR = r + dr;
		int nextC = c + dc;

		if (count + 1 == N) {
			if (visited[nextR][nextC]) answer++;
			continue;
		}
		if (!visited[nextR][nextC]) {
			visited[nextR][nextC] = 1;
			DFS(nextR, nextC, count + 1, now);
			visited[nextR][nextC] = 0;
		}
		
	}
}
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> N;

	//0 번째 이동 50,50 -> 49,50
	visited[50][50] = 1;
	visited[49][50] = 1;
	DFS(49, 50, 0, 0);
	
	cout << answer << endl;
	return 0;
}

결과