[C++] 육각형 우리 속의 개미 (백준 17370번)

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

 

 

각 이동은 위와 같이 벡터로 표현할 수 있다. 실수 좌표계에서 방문 처리를 하는 법은 여러 방법이 있을 수 있겠지만 나는 두가지 방법으로 구현해보았다. 

1. 실수 좌표를 그대로 사용, 대신 오차 범위를 두고 비교

벡터는 동일하게 (1, 0) (0.5, sqrt(3)/2), (-0.5, sqrt(3)/2), ... 이런 식으로 계산한다. 다만 소수점 둘째자리 정도까지 반올림해주었다. 그래야 계산 상의 차이로 아주 작은 오차가 생겼을 때 같은 점으로 인식할 수 있다. 

나는 실수를 scale 후에 반올림을 해서 정수로 만들고, pair<int, int>을 원소로 하는 set으로 방문 처리를 해주었다. 

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;

double dx[6] = {1, 0.5, -0.5, -1, -0.5, 0.5};
double dy[6] = {0, sqrt(3)/2, sqrt(3)/2, 0, -sqrt(3)/2, -sqrt(3)/2};

int n;
set<pair<int, int>> vst;
int ans = 0;

pair<int, int> toKey(double x, double y, int scale = 100) {
    return {round(x * scale), round(y * scale)};
}

void dfs(double x, double y, int d, int cnt) {
    if (cnt > n) return;

    auto key = toKey(x, y);
    if (vst.count(key)) {
        if (cnt == n) ans++;
        return;
    }

    vst.insert(key);

    int newd1 = (d + 1) % 6;
    int newd2 = (d + 5) % 6;
    dfs(x + dx[newd1], y + dy[newd1], newd1, cnt + 1);
    dfs(x + dx[newd2], y + dy[newd2], newd2, cnt + 1);

    vst.erase(key);
}

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

    cin >> n;

    auto start = toKey(0, 0);
    vst.insert(start);
    dfs(dx[0], dy[0], 0, 0);

    cout << ans << '\n';
}

(AC)

2. 좌표 자체를 정수 기반으로 변환

벡터 자체를 (1, 0), (1, 1), (-1, 1), ... 이런 식으로 정수 기반으로 바꿔서 생각한다. 

그래서 정수 좌표계에서 방문 처리를 하는 것과 동일하게, 이차원 bool 배열로 방문 처리를 해주었다. 

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;

int dx[6] = {1, 1, -1, -1, -1, 1};
int dy[6] = {0, 1, 1, 0, -1, -1};

int n;
vector<vector<bool>> vst;
int ans = 0;

void dfs(double x, double y, int d, int cnt) {
    if (cnt > n) return;

    if (vst[x + 25][y + 25]) {
        if (cnt == n) ans++;
        return;
    }

    vst[x + 25][y + 25] = 1;

    int newd1 = (d + 1) % 6;
    int newd2 = (d + 5) % 6;
    dfs(x + dx[newd1], y + dy[newd1], newd1, cnt + 1);
    dfs(x + dx[newd2], y + dy[newd2], newd2, cnt + 1);

    vst[x + 25][y + 25] = 0;
}

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

    cin >> n;

    vst = vector<vector<bool>>(50, vector<bool>(50, 0));
    vst[0 + 25][0 + 25] = 1;
    dfs(dx[0], dy[0], 0, 0);

    cout << ans << '\n';
}

(AC)