백준 3654번: L퍼즐 [C++]

작성일 | In
다이아몬드 IV 다이아몬드 IV

문제

L퍼즐

2-SAT으로 환원해서 풀 수 있는 신기하고 재밌고 어려운 문제입니다.

저는 최대 유량과 2-SAT을 떠올렸으나 각 칸을 정점으로 하는 방식에 매몰되어 두 칸의 매칭을 정점으로 하는 방법을 떠올리지 못했습니다.

풀이

JusticeHui님의 블로그를 참고했습니다.

매칭

각각의 검은 칸은 위쪽 혹은 아래쪽의 하얀 칸을 하나 선택, 오른쪽 혹은 왼쪽의 하얀 칸을 하나 선택해야 하고, 이 선택들은 다른 선택과 겹치면 안 됩니다. 이 선택을 두 칸을 선으로 잇는 것으로 보고 매칭이라 하겠습니다. 임의의 매칭은 항상 검은 칸과 하얀 칸을 이어야 합니다.

검은 칸

검은 칸과 위쪽 하얀 칸을 잇는 매칭을 $U$, 같은 방식으로 왼쪽, 아래쪽, 오른쪽 하얀 칸을 잇는 매칭을 $L$, $D$, $R$이라 합시다.

조각은 L모양이므로 $U$와 $D$중 하나는 꼭 선택되어야 하고, $L$과 $R$중 하나는 꼭 선택되어야 합니다.

\[(U \lor D) \land (L \lor R)\]

$U$와 $D$를 모두 선택하면 검은 칸이 겹치므로 둘 중 하나는 선택하면 안 되고, $L$과 $R$의 경우도 마찬가지입니다.

\[(\neg U \lor \neg D) \land (\neg L \lor \neg R)\]

하얀 칸

동일한 하얀 칸과 다른 인접한 검은 칸을 잇는 임의의 두 매칭 $A$, $B$는 둘 모두 선택되면 안 됩니다. ($\neg A \lor \neg B$)

또한, L 모양 조각은 하얀 칸 두개와 검은 칸 하나로 이루어져 있으므로 하얀 칸의 개수는 정확히 검은 칸의 개수의 2배여야 합니다.

2-SAT

각 매칭은 하나의 정수로 나타낼 수 있습니다.

$(i, j)$와 $(i, j + 1)$의 매칭을 $mi + j$, $(i, j)$와 $(i + 1, j)$의 매칭을 $mi + j + nm$으로 나타냅시다.

어떤 칸 $c$와 왼쪽 칸의 매칭은 왼쪽 칸과 오른쪽 칸($c$)의 매칭과 같아야 하므로 자연스럽게 $(i, j)$와 $(i, j - 1)$의 매칭은 $mi + j - 1$, $(i, j)$와 $(i - 1, j)$의 매칭은 $(m(i - 1) + j + nm)$이 됩니다.

이와 같은 방식을 적절히 이용해서 2-SAT을 돌리면 해결할 수 있습니다. 그래프에서 총 정점의 개수는 $4nm$이므로 메모리 관리에 주의합시다.

코드

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
#include <bits/stdc++.h>
using namespace std;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};

int n, m, V;

constexpr int MX = 1010101;

vector<int> adj[MX];
bool finished[MX];
int visitOrder[MX], sccNum[MX];
vector<int> stk;

int visitedCnt = 0, sccCnt = 0;
bool satisfiable = true;

void initVariables() {
    V = 4 * n * m;

    for (int i = 0; i < V; i++)
        adj[i].clear();
    fill(finished, finished + V, false);
    fill(visitOrder, visitOrder + V, -1);
    fill(sccNum, sccNum + V, -1);

    visitedCnt = sccCnt = 0;
    satisfiable = true;
}

int findSCC(int cur) {
    stk.push_back(cur);
    visitOrder[cur] = visitedCnt++;
    int lowLink = visitOrder[cur];

    for (int nxt : adj[cur]) {
        if (finished[nxt])
            continue;

        if (visitOrder[nxt] == -1)
            lowLink = min(lowLink, findSCC(nxt));
        else
            lowLink = min(lowLink, visitOrder[nxt]);
    }

    if (lowLink == visitOrder[cur]) {
        while (true) {
            int top = stk.back();
            stk.pop_back();
            finished[top] = true;
            sccNum[top] = sccCnt;

            if (top == cur)
                break;
        }

        sccCnt++;
    }

    return lowLink;
}

// (x1 or x2)
void addClause(int x1, int x2) {
    x1 = (abs(x1) << 1) + (x1 >= 0);
    x2 = (abs(x2) << 1) + (x2 >= 0);

    adj[x1 ^ 1].push_back(x2);
    adj[x2 ^ 1].push_back(x1);
}

char pattern[555][555];

void solve() {
    cin >> n >> m;

    initVariables();

    int blackCnt = 0, whiteCnt = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cin >> pattern[i][j];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int id[4] = {
                (i - 1) * m + j - 1,          // R
                (i - 2) * m + j - 1 + n * m,  // U
                (i - 1) * m + j - 2,          // L
                (i - 1) * m + j - 1 + n * m   // D
            };

            bool isBlack[4] = {}, isWhite[4] = {};
            for (int k = 0; k < 4; k++) {
                isBlack[k] = (pattern[i + di[k]][j + dj[k]] == 'B');
                isWhite[k] = (pattern[i + di[k]][j + dj[k]] == 'W');
            }

            if (pattern[i][j] == 'B') {
                blackCnt++;

                for (int k = 0; k < 2; k++) {
                    if (isWhite[k] and isWhite[k + 2])
                        addClause(id[k], id[k + 2]),
                            addClause(-id[k], -id[k + 2]);
                    else if (isWhite[k])
                        addClause(id[k], id[k]);
                    else if (isWhite[k + 2])
                        addClause(id[k + 2], id[k + 2]);
                    else {
                        cout << "NO\n";
                        return;
                    };
                }
            } else if (pattern[i][j] == 'W') {
                whiteCnt++;

                for (int k = 1; k < 4; k++) {
                    for (int l = 0; l < k; l++) {
                        if (isBlack[k] and isBlack[l])
                            addClause(-id[k], -id[l]);
                    }
                }
            }
        }
    }

    for (int i = 0; i < V; i++) {
        if (finished[i])
            continue;
        findSCC(i);
    }
    for (int i = 0; i < V; i += 2) {
        if (sccNum[i ^ 1] == sccNum[i]) {
            satisfiable = false;
            break;
        }
    }

    if (whiteCnt == 2 * blackCnt and satisfiable)
        cout << "YES\n";
    else
        cout << "NO\n";
}

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

    int T;
    cin >> T;

    while (T--)
        solve();

    return 0;
}

백준 3654번: L퍼즐 [C++]