백준14737 Dev, Please Add This!

작성일 | In

문제 링크

  • http://icpc.me/14737

사용 알고리즘

  • SCC
  • 2-SAT

시간복잡도

  • $(HW)^2$

풀이

A에서 B로 간 다음 다시 B에서 A로 돌아오지 못하는 경우가 존재합니다. 그러므로 격자를 그래프로 만들 때 단방향 그래프를 만들어야 합니다.
A에서 B로 간 다음 다시 돌아오지 못할 수 있기 때문에, 어떤 SCC에 도착했다면 그 SCC에 있는 모든 별을 다 먹고 다른 SCC로 이동해야 합니다.

어떤 별 $x$를 먹을 수 있는 조건을 생각해봅시다. (별이 존재하는 SCC $x$에 갈 수 있는 조건이라고 생각해도 무방합니다.)
공은 가로방향 또는 세로방향으로 굴러갈 수 있기 때문에, $x$에 도달하기 위해서는 $x$의 가로 방향에 있는 SCC 혹은 세로 방향에 있는 SCC에 도달할 수 있어야 합니다. 또한 바로 위에 있는 SCC와 바로 아래에 있는 SCC는 같은 SCC이며, 바로 왼쪽에 있는 SCC와 바로 오른쪽에 있는 SCC도 같은 SCC입니다.
각 별을 먹기 위해서 방문해야 하는 SCC의 후보가 최대 2가지이기 때문에 2-SAT을 생각해볼 수 있습니다.

$i$번 SCC에 방문할 것이라면 변수 $A_i$를 참, 방문하지 않을 것이라면 $A_i$를 거짓으로 설정합시다.

  • 시작점이 포함된 컴포넌트 $s$에 대해서, $A_s$는 항상 참입니다.
  • $s$에서 도달하지 못하는 컴포넌트 $i$에 대해서, $A_i$는 항상 거짓입니다.
  • 서로 다른 두 컴포넌트 $i, j$에 대해 $i$와 $j$를 함께 방문할 수 없는 경우, $(￢A_i ∨ ￢A_j)$입니다.
  • 각 별 $x$에 대해, $x$를 먹기 위해서 컴포넌트 $i$ 또는 $j$를 방문해야하는 경우, $(A_i ∨ A_j)$입니다.

2-SAT을 돌려서 모순이 생기는지 확인하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};

int n, m, si, sj;
char a[55][55]; vector<p> star;
int mv[3030][2]; // 상하/좌우 이동
inline int id(int i, int j){ return i*50+j; }

struct Graph{
    vector<int> g[6060], r[6060], dfn; int chk[6060], pv;
    int inv(int x){ return x < 3030 ? x+3030 : x-3030; }
    void addEdge(int s, int e){ g[s].push_back(e); r[e].push_back(s); }
    void addCNF(int x, int y){ addEdge(inv(x), y); addEdge(inv(y), x); }

    void dfs(int v){ chk[v] = 1; for(auto i : g[v]) if(!chk[i]) dfs(i); dfn.push_back(v); }
    void rdfs(int v, int color){ chk[v] = color; for(auto i : r[v]) if(!chk[i]) rdfs(i, color); }
    int getSCC(const vector<int> &vertex){
        for(auto i : vertex) if(!chk[i]) dfs(i);
        reverse(all(dfn)); memset(chk, 0, sizeof chk);
        for(auto i : dfn) if(!chk[i]) rdfs(i, ++pv);
        return pv;
    }
    vector<p> getDAG(){
        vector<p> ret;
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(a[i][j] != '#') {
            int now = id(i, j);
            for(auto nxt : g[now]) if(chk[now] != chk[nxt]) ret.emplace_back(chk[now], chk[nxt]);
        }
        compress(ret); return move(ret);
    }
    int solve(){
        for(int i=1; i<3030; i++) if(chk[i] && chk[i+3030]) if(chk[i] == chk[i+3030]) return 0;
        return 1;
    }
} gph, dag, two_sat;

int able[6060][6060];
void bfs(int st){
    queue<int> q; q.push(st); able[st][st] = 1;
    while(q.size()){
        int v = q.front(); q.pop();
        for(auto i : dag.g[v]) if(!able[st][i]) able[st][i] = 1, q.push(i);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m; vector<int> vertex;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) {
        cin >> a[i][j];
        if(a[i][j] != '#') vertex.push_back(id(i, j));
        if(a[i][j] == 'O') si = i, sj = j;
        if(a[i][j] == '*') star.emplace_back(i, j);
    }

    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(a[i][j] != '#') {
        int now = id(i, j);
        for(int k=0; k<4; k++){
            int ii = i, jj = j;
            while(1 <= ii && ii <= n && 1 <= jj && jj <= m && a[ii][jj] != '#') ii += di[k], jj += dj[k];
            int nxt = id(ii-di[k], jj-dj[k]);
            gph.addEdge(now, nxt); mv[now][k/2] = nxt;
        }
    }

    int scc_cnt = gph.getSCC(vertex);
    auto compress_edge = gph.getDAG();
    for(auto i : compress_edge) dag.addEdge(i.x, i.y);
    for(int i=1; i<=scc_cnt; i++) bfs(i);

    int st = gph.chk[id(si, sj)]; two_sat.addCNF(st, st); // 시작점은 무조건 갈 수 있음 (A)
    for(int i=1; i<=scc_cnt; i++){
        if(!able[st][i]){ two_sat.addCNF(i+3030, i+3030); continue; } // 시작점에서 도달할 수 없는 SCC (not A)
        for(int j=1; j<=scc_cnt; j++){
            if(!able[i][j] && !able[j][i]) two_sat.addCNF(i+3030, j+3030); // 두 SCC를 동시에 방문할 수 없는 경우 (not A or not B)
        }
    }
    for(auto i : star){
        int v1 = mv[id(i.x, i.y)][0], v2 = mv[id(i.x, i.y)][1];
        two_sat.addCNF(gph.chk[v1], gph.chk[v2]); // 이 별을 먹기 위해서는 v1 혹은 v2를 방문해야 함 (v1 or v2)
    }

    vertex.clear();
    for(int i=1; i<=scc_cnt; i++) vertex.push_back(i), vertex.push_back(i+3030);

    two_sat.getSCC(vertex);
    if(two_sat.solve()) cout << "YES";
    else cout << "NO";
}