[c++] BOJ 17370 :: 육각형 우리 속의 개미

문제

육각형 우리 속의 개미 문제 바로가기

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

 

풀이

개미가 위치한 육각형의 점에 따라 TYPE1, TYPE2가 나올 수 있다.

 

육각형을 이렇게 3차원의 정사면체라고 생각하면 다음은 각각 x축으로 +1, y축으로 +1, z축으로 +1이다.

이러한 방식을 토대로 다음과 같은 흐름으로 코드를 구성하였다.

• (0, 0, 0)을 이미 들르고, z축 이동한 것(0, 0, 1)으로 처음 이동을 고정한다.
• 다음 이동부터는 TYPE에 따라 3가지 방향으로 이동할 수 있다.
  • 만일 현재 TYPE 1의 x축 방향으로 이동했다면,
  • 다음 턴에 TYPE 2의 방향들로 이동할 수 있고
  • TYPE 2의 방향 중 x축 방향(방금 건너온 방향)으로는 돌아가지 않는다.
  • 따라서 각 TYPE의 방향이 3가지이므로, 각 턴에 가능한 개미의 진행방향은 2가지이다.
• 이동 중에 이미 방문한 점을 다시 방문했다면
  • 현재 방향 전환 횟수가 목표한 방향 전환 횟수인지 확인하고
    • 맞다면 정답의 개수를 +1한다.
    • 아니라면 탐색을 마친다.
• 이동 중 목표한 방향 전환 횟수를 초과하면 탐색을 마친다.

 

코드

#include <iostream>

using namespace std;

int directionTypeOne[3][3] = { {-1, 0, 0}, {0, -1, 0}, {0, 0, -1} };
int directionTypeTwo[3][3] = { {1, 0, 0}, {0, 1, 0}, {0, 0, 1} };

int N;
int result = 0;
int visited[46][46][46]; // 음수까지 표현

bool isInitialPos(int x, int y, int z) {
    return (x == 0) && (y == 0) && (z == 0);
}

void dfs(int x, int y, int z, bool type, int xyzWhich, int cnt) {
    if (visited[x + 22][y + 22][z + 22] == 1) { // 이전에 방문 한 곳
        if (cnt == N)
            result++;
        return; // 탐색 끝
    }

    if (cnt > N) {
        return;
    }

    visited[x + 22][y + 22][z + 22] = 1;

    auto directionArr = (type ? directionTypeOne : directionTypeTwo);
    for (int i = 0; i < 3; i++) {
        if (i == xyzWhich) continue; // 같은 방향으로 되돌아가지 않음

        int xNew = x + directionArr[i][0];
        int yNew = y + directionArr[i][1];
        int zNew = z + directionArr[i][2];

        dfs(xNew, yNew, zNew, !type, i, cnt+1);
    }

    visited[x + 22][y + 22][z + 22] = 0;
}

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

    // N번만에 개미는 제자리로 돌아와야 함
    // 방향에 따라서 같은 경로도 다를 수 있음 => 점을 방문하는 순서
    // 방향은 처음엔 3가지, 다음부터는 본인이 온 경로를 제외한 2가지 (x, y, z로 생각)

    cin >> N;
    fill(&visited[0][0][0], &visited[45][45][46], 0);
    visited[22][22][22] = 1; // 시작점 => 주의!
    dfs(0, 0, 1, true, 2, 0);// 첫번째 경로는 고정
    cout << result;
}

 

 

결과

아이디	메모리	시간	코드 길이
gmldms784	2400	44	1461