[Algorithm] C++ 백준 14737번 Dev, Please Add This!

아이디어 요약

단순히 “별이 한 번이라도 어떤 굴림 경로에 포함되면 OK”가 아니다. 한 번의 플레이 순서로 전부 먹을 수 있어야 하므로 순서 제약이 존재한다.
각 빈 칸을 정점으로 하고, 네 방향으로 굴려 도착하는 “정지 칸"으로의 간선을 두면 단방향 그래프가 된다.
그래프를 SCC로 압축해 DAG를 만든다. 어떤 두 컴포넌트가 서로 도달 불가능하면 한 플레이에서 두 컴포넌트를 모두 방문하는 것은 불가능하다.
각 별은 그 칸에서 수직/수평으로 굴러서 멈추는 정지 칸의 컴포넌트 중 적어도 하나를 방문해야 먹을 수 있다.
따라서 “컴포넌트 i를 방문한다/안 한다”를 변수로 잡고, 2-SAT 제약을 구성한다.
- 시작 컴포넌트는 반드시 방문 (참 고정). 시작에서 도달 불가능한 컴포넌트는 방문 금지 (거짓 고정).
- DAG에서 서로 도달 불가능한 두 컴포넌트 i, j는 동시에 방문 불가 → (¬A_i ∨ ¬A_j).
- 각 별 x는 (A_row(x) ∨ A_col(x)). 여기서 row/col은 해당 칸에서 수평/수직으로 굴린 정지 칸의 컴포넌트.
2-SAT이 만족 가능하면 YES, 아니면 NO.

C++ 풀이

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

struct TwoSAT {
    int numVars;
    vector<vector<int>> g, rg;
    vector<int> comp, order;

    TwoSAT(int n = 0) { init(n); }
    void init(int n) {
        numVars = n;
        g.assign(2 * n, {});
        rg.assign(2 * n, {});
    }
    static int varFalse(int i) { return 2 * i; }
    static int varTrue(int i) { return 2 * i + 1; }
    static int Not(int x) { return x ^ 1; }

    void addImp(int u, int v) { g[u].push_back(v); rg[v].push_back(u); }
    void addOr(int A, int B) { addImp(Not(A), B); addImp(Not(B), A); }
    void forceTrue(int L) { addOr(L, L); }
    void forceFalse(int L) { addOr(Not(L), Not(L)); }

    bool satisfiable(vector<int>* assignment = nullptr) {
        int N = 2 * numVars;
        vector<int> vis(N, 0); order.clear(); order.reserve(N);
        function<void(int)> dfs1 = [&](int v) {
            vis[v] = 1;
            for (int to : g[v]) if (!vis[to]) dfs1(to);
            order.push_back(v);
        };
        for (int i = 0; i < N; ++i) if (!vis[i]) dfs1(i);

        comp.assign(N, -1); int cc = 0;
        function<void(int)> dfs2 = [&](int v) {
            comp[v] = cc;
            for (int to : rg[v]) if (comp[to] == -1) dfs2(to);
        };
        for (int i = N - 1; i >= 0; --i) {
            int v = order[i];
            if (comp[v] == -1) { dfs2(v); ++cc; }
        }
        for (int i = 0; i < numVars; ++i) if (comp[2 * i] == comp[2 * i + 1]) return false;
        if (assignment) {
            assignment->assign(numVars, 0);
            for (int i = 0; i < numVars; ++i)
                (*assignment)[i] = comp[2 * i] < comp[2 * i + 1] ? 1 : 0;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W; if (!(cin >> H >> W)) return 0;
    vector<string> grid(H);
    for (int i = 0; i < H; ++i) cin >> grid[i];

    const int dr[4] = {1, -1, 0, 0};
    const int dc[4] = {0, 0, 1, -1};
    auto inb = [&](int r, int c) { return 0 <= r && r < H && 0 <= c && c < W; };

    vector<int> id(H * W, -1);
    vector<pair<int,int>> cells; cells.reserve(H * W);
    pair<int,int> start = {-1, -1};
    vector<pair<int,int>> stars;

    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) {
            if (grid[r][c] != '#') {
                id[r * W + c] = (int)cells.size();
                cells.push_back({r, c});
                if (grid[r][c] == 'O') start = {r, c};
                if (grid[r][c] == '*') stars.push_back({r, c});
            }
        }
    }
    int N = (int)cells.size();
    if (N == 0) { cout << "NO\n"; return 0; }

    auto rollStop = [&](int r, int c, int d) {
        int nr = r, nc = c;
        while (true) {
            int tr = nr + dr[d], tc = nc + dc[d];
            if (!inb(tr, tc) || grid[tr][tc] == '#') break;
            nr = tr; nc = tc;
        }
        return pair<int,int>{nr, nc};
    };

    vector<vector<int>> g(N), rg(N);
    vector<array<int,2>> mv(N, array<int,2>{-1, -1}); // 0: vertical, 1: horizontal

    for (int v = 0; v < N; ++v) {
        auto [r, c] = cells[v];
        for (int d = 0; d < 4; ++d) {
            auto [sr, sc] = rollStop(r, c, d);
            int u = id[sr * W + sc];
            g[v].push_back(u);
            rg[u].push_back(v);
            mv[v][d / 2] = u; // up/down -> 0, right/left -> 1
        }
    }

    // Kosaraju SCC
    vector<int> order, vis(N, 0);
    function<void(int)> dfs1 = [&](int v) {
        vis[v] = 1;
        for (int to : g[v]) if (!vis[to]) dfs1(to);
        order.push_back(v);
    };
    for (int v = 0; v < N; ++v) if (!vis[v]) dfs1(v);

    vector<int> comp(N, -1); int sccCnt = 0;
    function<void(int)> dfs2 = [&](int v) {
        comp[v] = sccCnt;
        for (int to : rg[v]) if (comp[to] == -1) dfs2(to);
    };
    for (int i = N - 1; i >= 0; --i) {
        int v = order[i];
        if (comp[v] == -1) { dfs2(v); ++sccCnt; }
    }

    // Build SCC DAG
    vector<vector<int>> dag(sccCnt);
    vector<int> indeg(sccCnt, 0);
    {
        vector<unordered_set<int>> uniq(sccCnt);
        for (int v = 0; v < N; ++v) {
            int a = comp[v];
            for (int to : g[v]) {
                int b = comp[to];
                if (a != b && uniq[a].insert(b).second) {
                    dag[a].push_back(b);
                    indeg[b]++;
                }
            }
        }
    }

    // Topological order
    queue<int> q; for (int i = 0; i < sccCnt; ++i) if (indeg[i] == 0) q.push(i);
    vector<int> topo; topo.reserve(sccCnt);
    while (!q.empty()) {
        int v = q.front(); q.pop(); topo.push_back(v);
        for (int to : dag[v]) if (--indeg[to] == 0) q.push(to);
    }

    // DAG reachability via bitset DP
    const int MAXS = 2600; // 50*50 <= 2500
    vector<bitset<MAXS>> reach(sccCnt);
    for (int i = sccCnt - 1; i >= 0; --i) {
        int v = topo[i];
        reach[v].set(v);
        for (int to : dag[v]) reach[v] |= reach[to];
    }

    // 2-SAT variables: one per SCC (Ai = visit SCC i)
    TwoSAT sat(sccCnt);

    int startId = id[start.first * W + start.second];
    int s = comp[startId];
    sat.forceTrue(TwoSAT::varTrue(s));
    for (int i = 0; i < sccCnt; ++i) if (!reach[s].test(i)) sat.forceFalse(TwoSAT::varTrue(i));

    // Incomparable pairs cannot both be visited: (¬Ai ∨ ¬Aj)
    for (int i = 0; i < sccCnt; ++i) {
        for (int j = i + 1; j < sccCnt; ++j) {
            if (!reach[i].test(j) && !reach[j].test(i)) {
                sat.addOr(TwoSAT::varFalse(i), TwoSAT::varFalse(j));
            }
        }
    }

    // For each star, must visit vertical or horizontal stopping SCC
    for (auto [r, c] : stars) {
        int v = id[r * W + c];
        int vVert = comp[mv[v][0]];
        int vHori = comp[mv[v][1]];
        sat.addOr(TwoSAT::varTrue(vVert), TwoSAT::varTrue(vHori));
    }

    cout << (sat.satisfiable() ? "YES\n" : "NO\n");
    return 0;
}