[BOJ] 34006 사계절을 되찾은 자

문제 요약

문제 링크: 백준 34006 - 사계절을 되찾은 자

문제 설명

---

접근 방법

A값은 봄의 기운, B값은 여름의 기운, C값은 가을의 기운이다. 문제에서 이 값들은 모두 0보다 크거나 2N보다 작아야만 한다고 주어졌다. 이 조건을 만족시키면서 초기 A,B,C 모두의 값이 N이 될 때까지 BFS로 탐색을 해주면 된다. 

문제를 푸는데 필요했던 테크닉은 크게 2가지이다.

• A, B, C 3개의 값을 모두 탐색을 해줄 수 없다. 1부터 1999까지의 값을 가질 수 있기 때문에 방문 배열을 vis[2000][2000][2000] 이런식으로 잡게 된다면 메모리가 부족할 것이다. 따라서 A+B+C는 항상 3N 값인 것을 활용해야 한다. 그렇게 했을 때 각각의 상태 값 방문 배열은 A와 B만 기록하면 된다. A와 B의 값에 따라 자동으로 C값도 정해져 있기 때문이다.
• 문제의 주어진 출력에서 공격 패턴을 사전순으로 출력하라는 내용이 있다. 따라서 BFS를 탐색할 때, 궁기의 공격, 도올의 공격, 혼돈의 공격 순으로 확정시켜야 하고, 경로 역추적을 위한 배열도 추가로 필요하다. 

경로 역추적이 필요한 이유는, 큐에 공격 패턴을 담은 문자열을 넣으면, 매 공격시 문자열 복사가 큐에서 일어나기에 시간초과가 나기 때문이다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, A, B, C, a, b, c;
bool vis[2001][2001]; // a와 b의 방문처리
pair<char,pair<int,int>> mat[2001][2001];  // 경로 역추적 용

void solve() {
    queue<tuple<int, int, int>>q;
    q.push({ A,B,C });
    vis[A][B] = 1;
    mat[A][B].first = 'E';  // 시작 경로, 임의로 'E'로..
    while (q.size()) {
        int a1 = get<0>(q.front());
        int b1 = get<1>(q.front());
        int c1 = get<2>(q.front());
        q.pop();
        if (a1 == n && b1 == n) {
            vector<char>ans;
            while (mat[a1][b1].first != 'E') {
                int a2 = a1, b2 = b1;
                ans.push_back(mat[a1][b1].first);
                a1 = mat[a2][b2].second.first;
                b1 = mat[a2][b2].second.second;
            }
            cout << ans.size() << '\n';
            reverse(ans.begin(), ans.end());
            for (auto i : ans) cout << i;
            return;
        }
        if (a1 + a < 2 * n && c1 - a > 0) {  // 궁기의 공격
            int a2 = a1 + a;
            int c2 = c1 - a;
            int b2 = n * 3 - (a2 + c2);
            if (b2 < 2 * n && b2 > 0) {
                if (!vis[a2][b2]) {
                    q.push({ a2,b2,c2 });
                    vis[a2][b2] = 1;
                    mat[a2][b2].first = 'A';
                    mat[a2][b2].second = { a1,b1 };
                }
            }
        }
        if (b1 + b < 2 * n && a1 - b > 0) {  // 도올의 공격
            int b2 = b1 + b;
            int a2 = a1 - b;
            int c2 = n * 3 - (b2 + a2);
            if (c2 < 2 * n && c2 > 0) {
                if (!vis[a2][b2]) {
                    q.push({ a2,b2,c2 });
                    vis[a2][b2] = 1;
                    mat[a2][b2].first = 'B';
                    mat[a2][b2].second = { a1,b1 };
                }
            }
        }
        if (c1 + c < 2 * n && b1 - c > 0) {  // 혼돈의 공격
            int c2 = c1 + c;
            int b2 = b1 - c;
            int a2 = n * 3 - (c2 + b2);
            if (a2 < 2 * n && a2 > 0) {
                if (!vis[a2][b2]) {
                    q.push({ a2,b2,c2 });
                    vis[a2][b2] = 1;
                    mat[a2][b2].first = 'C';
                    mat[a2][b2].second = { a1,b1 };
                }
            }
        }
    }
    cout << -1;
}

void input() {
    cin >> n >> A >> B >> C >> a >> b >> c;
}

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