PS

백준 18535 : Tomb raider

jyheo98 2021. 1. 27. 10:03

 

문제 링크 : www.acmicpc.net/problem/18535

 

사용 알고리즘 : DSU, 구현

 

 

가고일 배치도

 

관찰) G 위치 두 곳에 가고일이 있다고 해보자. 두 가고일은 서로 거울에 의해 보일 수 있는 위치에 놓여있다.

이 떄, 한 가고일을 특정 방향으로 고정시키면, 다른 가고일의 방향도 무조건 고정되는 것을 알 수 있다. (그렇지 않으면 한 가고일이 다른 가고일의 옆면을 보게 된다.)

 

이는 가고일이 두마리가 아니라 여러마리여도 확장할 수 있는 개념이다. 서로 거울로, 혹은 그냥 공기로 연결된 가고일들끼리는, 한 가고일의 방향만 결정해주면 나머지 가고일의 방향은 자동으로 결정된다는 것이다.

 

따라서 연결된 가고일끼리 DSU로 부모를 같게 해준 뒤, 원래 orientation에서 바뀌는 정도의 cost를 계산해 주면 답을 계산할 수 있다.

그리고 몇몇 가고일은 특정 방향을 바라보면 장애물을 마주보게 되는데, 이 때 드는 cost를 무한대로 만들어주었다.

 

구현을 천천히 해서 실수없이 풀어야 한 문제였다. 아이디어는 금방 나왔는데, 구현에 이틀이 걸렸다.

 

우선 각 가고일에 번호를 붙인 뒤, 가로로 놓인 가고일 = 번호 * 2 - 1, 세로로 놓인 가고일 = 번호 * 2로 붙인 뒤 dsu를 통해 연결된 가고일의 부모를 같게 만들어 주었다.

 

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
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")
 
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
 
using pii = pair<intint>;
using ll = long long;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
 
int D=0,R=1,U=2,L=3;
vector<int> dx = {1,0,-1,0}, dy= {0,1,0,-1};
int par[500500];
int cost[1000100];
 
int find(int x) {
    if(x==par[x]) return x;
    return par[x] = find(par[x]);
}
 
void merge(int u, int v) {
    u = find(u); v = find(v);
    if(u > v) swap(u,v);
    par[v] = u;
}
 
void solve() {
    int n, m; cin >> n >> m;
    vector<string> s(n);
    for(int i=0 ; i<n ; i++) {
        cin >> s[i];
    }    
    int idx = 1;
    vector<vector<int>> id(n, vector<int>(m));
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<m ; j++) {
            if(s[i][j] == 'V' || s[i][j] == 'H') {
                cost[idx*2-1]=(s[i][j]=='V');
                cost[idx*2]=(s[i][j]=='H');
                id[i][j] = idx;
                idx += 1;
            }
        }
    }
 
    for(int i=0 ; i<500020 ; i++
        par[i] = i;
 
    function<int(int,int,int)> simulate = [&](int x, int y, int dir) {
        while(1) {
            x += dx[dir]; y += dy[dir];
            if(x < 0) {
                x = 0; dir = D;
            } else if(x >= n) {
                x = n-1; dir = U;
            } else if(y < 0) {
                y = 0; dir = R;
            } else if(y >= m) {
                y = m-1; dir = L;
            }
            if(id[x][y]) {
                if(dir==L||dir==R) 
                    return id[x][y] * 2 - 1;
                else
                    return id[x][y] * 2;
            }
            if(s[x][y]=='#'return -1;
            if(s[x][y]=='/') {
                if(dir == U) dir = R;
                else if(dir == R) dir = U;
                else if(dir == L) dir = D;
                else if(dir == D) dir = L;
            }
            if(s[x][y]=='\\') {
                if(dir==U) dir = L;
                else if(dir==L) dir = U;
                else if(dir==D) dir = R;
                else if(dir==R) dir = D;
            }
        }
        return -1;
    };
 
    // horizontal : 1, 3, 5, ...
    // vertical : 2, 4, 6, ...
 
    auto rvs = [](int x) {
        if(x % 2
            return x + 1;
        else
            return x - 1;
    };
 
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<m ; j++) { if(id[i][j]) 
            for(int dir=0 ; dir<4 ; dir++) {
                int cur = id[i][j] * 2 - (dir==L||dir==R);
                int nxt = simulate(i,j,dir);
                if(nxt == -1) cost[cur] = INF;
                else {
                    merge(cur,nxt);
                    merge(rvs(cur),rvs(nxt));
                }
            }        
        }
    }
 
    idx-=1;
    for(int i=1 ; i<=idx*2 ; i+=2) {
        if(find(i)==find(i+1)) {
            cout << -1 << "\n";
            return;
        }
    }
 
    vector<vector<int>> z(idx*2+100);
    for(int i=1 ; i<=idx*2 ; i++) {
        int par = find(i);
        z[par].push_back(i);
    }
 
    ll ans = 0;
 
    for(int i=1 ; i<=idx*2 ; i++) {
        ll ans1 = 0, ans2 = 0;
        for(auto x : z[i]) {
            ans1 += cost[x];
            ans2 += cost[rvs(x)];
        }
        if(ans1>=INF&&ans2>=INF) {
            cout << -1 << "\n";
            return;
        }
        ans += min(ans1, ans2);
    }
    cout << ans / 2 << "\n";
}
 
int main() {
    IOS;
    int t = 1;
    while(t--)
        solve();
}
cs