백준20031 Remote Control

작성일 | In

문제 링크

  • http://icpc.me/20031

사용 알고리즘

  • Union Find

시간복잡도

  • $O(N + Q \log Q)$

풀이

모든 좌표(쿼리)를 입력 받은 다음, 한 번에 처리하는 오프라인 방식으로 문제를 풉니다.
각 턴마다 차 Q대를 모두 이동시키는 것은 무리같으니 반대로 벽을 움직인다고 생각합시다.

만약 어떤 차가 벽이랑 충돌하면 그 행동은 취소됩니다. 이는 충돌하게 되는 차도 같이 벽이 이동하는 방향으로 밀어주는 것으로 구현할 수 있습니다.
이 행위로 인해 어떤 두 차가 동일한 칸에 속하게 된다면 그 시점 이후에도 계속 같은 칸에 속합니다. 이런 차들은 Union Find로 묶어서 관리해주면 됩니다.

답을 출력할 때는 벽과 차의 위치를 적당히 평행이동해서 출력하면 됩니다.

전체 코드

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
#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;

// L R U D
const int dy[] = {0, 0, 1, -1};
const int dx[] = {-1, 1, 0, 0};
inline int dir(char c){
    if(c == 'L') return 0;
    if(c == 'R') return 1;
    if(c == 'U') return 2;
    return 3;
}

int par[303030]; p pos[303030];
map<p, int> mp;
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
void merge(int u, int v){ u = find(u); v = find(v); if(u != v) par[u] = v; }

int n, q; string s;
p qry[303030];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> s >> q;
    for(int i=1; i<=q; i++) cin >> qry[i].x >> qry[i].y;
    iota(par, par+303030, 0);
    for(int i=1; i<=q; i++){
        pos[i] = qry[i];
        if(!mp.count(pos[i])){ mp[pos[i]] = i; continue; }
        int t = mp[pos[i]]; mp.erase(pos[i]);
        merge(i, t); t = find(t); mp[pos[t]] = t;
    }

    int x = 0, y = 0;
    for(auto i : s){
        int d = (dir(i) ^ 1);
        x += dx[d]; y += dy[d];
        if(!mp.count(p(x, y))) continue;
        int t = mp[p(x, y)]; mp.erase(pos[t]);
        pos[t].x += dx[d]; pos[t].y += dy[d];
        if(!mp.count(pos[t])){ mp[pos[t]] = t; continue; }
        int tt = mp[pos[t]]; mp.erase(pos[t]);
        merge(t, tt); t = find(t); mp[pos[t]] = t;
    }
    for(int i=1; i<=q; i++) cout << pos[find(i)].x-x << " " << pos[find(i)].y-y << "\n";
}