백준 17370번 풀이

육각형 형태를 좌표평면에 대응시킵니다.

 

입력 제한이 22이므로... 아무리 멀리 나가더라도 상하좌우로 50을 벗어날 수 없겠죠.

 

버퍼를 50*50으로 받고... DFS로 백트래킹해서 답을 구해냅니다.

 

시간복잡도는 O(2^n)

 

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
#include <list>
#include <stack>

using namespace std;


struct Point {
    int x;
    int y;

    int previousX;
    int previousY;

    bool type;
    vector<Point> nextPoints() {
        vector<Point> candidate;
        if (type) {
            int delta[3][2] = { {-1, 0}, {1, 1}, {1, -1} };

            for (auto i=0; i<3; i++) {
                Point aPoint;
                aPoint.type = false;
                aPoint.previousX = x;
                aPoint.previousY = y;
                aPoint.x = x + delta[i][0];
                aPoint.y = y + delta[i][1];
                if (!(aPoint.x == previousX && aPoint.y == previousY)) {
                    candidate.push_back(aPoint);
                }
            }
        } else {
            int delta[3][2] = { {1, 0}, {-1, 1}, {-1, -1} };

            for (auto i=0; i<3; i++) {
                Point aPoint;
                aPoint.type = true;
                aPoint.previousX = x;
                aPoint.previousY = y;
                aPoint.x = x + delta[i][0];
                aPoint.y = y + delta[i][1];
                if (!(aPoint.x == previousX && aPoint.y == previousY)) {
                    candidate.push_back(aPoint);
                }
            }
        }
        return candidate;
    }

};

class AntManager {
public:
    AntManager(int n) {
        this->n = n;
        for (auto i=0; i<50; i++) {
            for (auto j=0; j<50; j++) {
                isVisited[i][j] = false;
            }
        }
    }

    int findRoute() {
        isVisited[25][25] = true;
        isVisited[26][26] = true;
        Point startPoint;
        startPoint.previousX = 25;
        startPoint.previousY = 25;
        startPoint.x = 26;
        startPoint.y = 26;
        startPoint.type = false;

        if (n == 1) {
            return 0;
        }
        dfs(1, startPoint);
        return answer;
    }

    void dfs(int currentRound, Point currentPoint) {
//        cout << currentPoint.x -25 << ' ' << currentPoint.y -25 <<' ' << currentRound<<'\n';
        auto points = currentPoint.nextPoints();

        if (currentRound == n) {

            for (auto point: points) {
                if (isVisited[point.x][point.y]) {
                    this->answer++;
                }
            }

        } else {
            for (auto point: points) {
                if (!isVisited[point.x][point.y]) {
                    isVisited[point.x][point.y] = true;
                    dfs(currentRound+1, point);
                    isVisited[point.x][point.y] = false;
                }
            }

        }

    }



private:
    int answer = 0;
    int n;
    bool isVisited[50][50];
};

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


    int n;
    cin >> n;
    AntManager * manager = new AntManager(n);
    cout << manager->findRoute();
    return 0;
}