백준 17370번 육각형 우리 속의 개미

문제

문제 분석

일반적인 벌집 모양 문제이다. 다만 처음에 종료조건을 조금 오인했는데, 하나의 벌집 칸을 모두 돌 때 끝나는 것이 아닌, 이미 지나온 어떠한 칸을 마주치더라도 종료되는 것이다. 그래서 그냥 좌표에다가 벌집을 찍고, 회전에 대한 구현을 하여 이미 지나온 점을 만날 때 회전한 횟수가 P일 때 카운트를 더하게 하여 문제를 해결하였다.

 

우선 벌집을 좌표로써 표현한 방법은, 가로와 세로로 나눌 수 있는데, 세로의 경우, 한 변의 길이가 a라고 가정했을 때, 직선으로 올라가는 것, 대각선으로 올라가는 것 (내려가는 것 포함)으로 나눌 수 있다. 직선으로는 y좌표로 그대로 a가 추가되고, 대각선으로는 a * 1/2가 추가된다 (30, 60, 90 직사각형으로 보았을 때 길이의 비율로 따짐).

가로로 보았을 때는 대각선으로 이동할 때 밖에 없는데, 30, 60, 90 직사각형으로 때내어 보았을 때 a * sqrt(3)/2 이다. 그런데 어차피 가로는 대각선으로 움직일 경우에만 바뀌므로, 이 값을 다른 값으로 치환해도 문제가 없다. 즉 정육각형이 아닌, 가로가 조금 더 좁은 육각형의 모습으로 변환하는 것이다.

 

이렇게 좌표계에 나타낸 벌집에 회전을 구현해주었는데, 벌집 내부에서 회전하는 경우의 수는 6개이고, 각 회전 경우에 대해서 회전 가능한 경우는 시계방향(+1) 과 반시계방향(-1)이므로 이를 offset으로 잘 나타내어 회전을 구현하였다.

 

 

 

코드

// code
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<list>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;

int dfs(int param_count, int continuous_count)
{
    if(param_count + continuous_count < 6 || param_count < 0)
        return 0;
    if(continuous_count == 6 && param_count == 0)
        return 1;
    return dfs(param_count-1, continuous_count+1) + dfs(param_count-1, 1);
}

int offset[6][2] = {{-1, 2}, {1, 2}, {3, 0}, {1, -2}, {-1, -2}, {-3, 0}};
int my_map[200][200] = {0};
int n;
int result = 0;
int travle(int param_x, int param_y, int param_dir, int param_count)
{
    param_x += offset[param_dir][0];
    param_y += offset[param_dir][1];
    if(my_map[param_y][param_x] == 1)
    {
        if(param_count == n)
        {
            result++;
            return 1;
        }
        else
            return 0;
    }
    if(param_count >= n)
        return 0;
    my_map[param_y][param_x] = 1;
    int return_val = 0;
    return_val += travle(param_x, param_y, (param_dir+1)%6, param_count+1);
    return_val += travle(param_x, param_y, (param_dir+5)%6, param_count+1);
    my_map[param_y][param_x] = 0;
    return return_val;
}

void solution()
{
    // code
    int now_dir = 1;
    int now_x = 100;
    int now_y = 100;
    cin >> n;
    my_map[now_y][now_x] = 1;
    cout << travle(100, 100, 1, 0);
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

벌집문제의 직관을 빨리 떠올리도록 하자.