[백준 14932] 금고(SAFE)

문제

www.acmicpc.net/problem/14932

 

알고리즘

Union-find

 

풀이

버튼을 순차적으로 나갈 때, 금고를 풀 수 있는지 묻는 문제입니다.

 

하나의 노드에서 다른 노드로 간다. 라는 점에서 다양한 풀이들을 떠올릴 수 있습니다. 저는 처음에 SCC로 접근하여 컴포넌트의 수를 카운트하여 답을 계산하였습니다. 다른 풀이로는 하나의 노드를 자식으로 다른 노드를 부모로 설정하여

유니온 파인드로 접근하는 것입니다.

 

각 버튼의 고유값을 매기기 위해 순차적으로 번호를 매겼습니다. (r,c)에 해당하는 번호는 $r*N+j$ 이 됩니다. 입력을 받아 현재 자신이 어디의 버튼을 가리키고 있는지 찾습니다. 그리고 부모-자식관계로 묶어줍니다.  그리고 부모-자식관계가 성립하지 못한 버튼이 있다면 카운트를 해줍니다. 이 버튼의 의미는 무조건 여기서 시작을 해야하는 버튼입니다. 이 버튼의 수가 2를 넘는다면 금고는 절대 풀지 못합니다.

 

버튼이 1개일 때, 그 버튼에서부터 시뮬레이션을 시작합니다. 이 때, 유니온 파인드로 시뮬레이션 결과를 $O(1)$에 찾을 수 있습니다. 이 버튼을 $k$라고 한다면 $k$에서 시작하여 거쳐간 버튼의 수는 $find(k)$의 $p$배열에 담겨 있습니다.

 

버튼의 수가 0 이라면 임의의 버튼에서 시작하여 시뮬레이션 하면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int dy[4] = { -1, 0, 1, 0 };
const int dx[4] = { 0, 1, 0, -1 };
const int MAXN = 1e6;

int N;
int conv[128];
int nxt[MAXN], pointed[MAXN], visited[MAXN], p[MAXN];

int find(int x) {
    return p[x] < 0 ? x : p[x] = find(p[x]);
}

void _union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    p[a] += p[b];
    p[b] = a;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    conv['U'] = 0;
    conv['R'] = 1;
    conv['D'] = 2;
    conv['L'] = 3;

    cin >> N;
    memset(p, -1, sizeof(p));
    rep(i, N * N) {
        int d;
        char c;
        cin >> d >> c;
        nxt[i] = i + dy[conv[c]] * N * d + dx[conv[c]] * d;
        pointed[nxt[i]]++;
        _union(i, nxt[i]);
    }

    int cnt = 0, pos = 0;
    rep(i, N * N) if (!pointed[i]) {
        pos = i;
        ++cnt;
    }

    if (cnt >= 2) {
        cout << "TOO SAFE";
        return 0;
    }
    int node = -p[find(pos)];

    if (node == N * N) {
        if (cnt == 0)
            cout << "THIEF LOVE IT!";
        else
            cout << pos / N + 1 << ' ' << pos % N + 1;
    } else {
        cout << "TOO SAFE";
    }
    return 0;
}