티스토리 뷰

알고리즘 관련/UVaOJ

UVaOJ)12460 Careful teacher

JASON 자손9319 2017. 6. 17. 19:30

문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3891


문제를 간략하게 설명하면 사전에 존재하는 단어들이 주어진 뒤 쿼리가 들어올 때


쿼리에서 들어오는 두 단어를 A와 B라고할 때 A를 B로 바꿀 수 있는지 여부를 물어보는 문제이다.


이 때 A를 B로 바꾸는 경우는 한글자 씩 바꿀 수 있으며 단, 한글자를 바꾼 단어도 사전에 존재하여야만 바꿀 수 있다.


이 문제는 사전에 존재하는 단어들을 정점으로 생각하고 1글자 다른 단어들을 간선으로 묶어주면 


A와 B가 같은 컴포넌트에 존재하는지 여부를 묻는 문제로 변형된다.


이는 disjoint-set을 통하여 해결해줄 수 있다.


N제한이 20000이지만 시간제한이 8초이고.. 데이터가 생각보다 약한것 같기 때문에 N*N으로 merge를 해줄 수 있다.


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
#include <cstdio>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
using namespace std;
char a[20010][55];
int n, len[20020], par[20010];
char x[55], y[55];
map<string, int> mp;
int find(int h) {
    return h == par[h] ? h : par[h] = find(par[h]);
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    par[x] = y;
}
int main() {
    while (1) {
        scanf("%s"&a[++n]);
        for (len[n]; a[n][len[n]]; len[n]++) {
            a[n][len[n]];
        }
        if (len[n] == && a[n][0== '-'&&a[n][1== '-')
            break;
        mp[a[n]] = n;
    }
    n--;
    for (int i = 1; i <= n; i++)
        par[i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (len[i] != len[j])continue;
            int cnt = 0;
            for (int k = 0; a[i][k]; k++) {
                if (a[i][k] != a[j][k])
                    cnt++;
            }
            if (cnt == 1)
                merge(i, j);
        }
    }
    while (scanf("%s %s"&x, &y) != EOF) {
        if (mp.find(x) == mp.end() || mp.find(y) == mp.end()) {
            puts("No");
            continue;
        }
        int xx = mp[x];
        int yy = mp[y];
        printf("%s\n", find(xx) == find(yy) ? "Yes" : "No");
    }
    return 0;
}
cs


'알고리즘 관련 > UVaOJ' 카테고리의 다른 글

UVaOJ)12159 Gun Fight  (0) 2017.06.27
UVaOJ)12878 Flowery Trails  (0) 2017.06.23
UVaOJ)10968 KuPellaKeS  (0) 2017.06.20
UVaOJ)12645 Water Supply  (0) 2017.06.19
UVaOJ)11751 Installing Diagnostic Software  (0) 2017.06.19
UVaOJ)12460 Careful teacher  (0) 2017.06.17
댓글
댓글쓰기 폼