ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 17370번 풀이
    백준 2019. 12. 3. 00:28

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

     

    입력 제한이 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;
    }

    '백준' 카테고리의 다른 글

    백준 1797번 C++ 풀이  (0) 2020.01.19
    백준 13460번 C++ 코드  (0) 2020.01.15
    백준 16681번 풀이  (0) 2019.12.01
    PS(알고리즘) 오픈 톡방 신입부원 대 모집!!  (0) 2019.12.01
    백준 14619번 c++ 풀이  (0) 2019.11.24

    댓글 0

Designed by Tistory.