티스토리 뷰

알고리즘 관련/BOJ

BOJ)1444 숌 언어

JASON 자손9319 2017. 7. 5. 15:39

문제:icpc.me/1444


대문자와 소문자가 번갈아 나타나는 문장이 주어질 때 대문자와 소문자로 이루어진 최소 몇개의 단어로 문장을 만들 수 있는지를 출력하는 문제이다.


이 문제는 (대문자,소문자)로 이루어진 단어와 (소문자,대문자)로 이루어진 단어의 이분 그래프로 나타내면 최소 버텍스 커버 문제로 치환하여 해결할 수 있다.


예를들어 AaAbBa라는 단어가 있을 때


Ab라는 정점과 bB라는 정점이 연결되고 bB라는 정점과 Ba라는 정점이 연결될 것이다.


이 연결을 할 수 있게 만드는 정점의 최소수를 구하는 문제이기 때문에 최소 버텍스 커버 문제로 해결 가능한 것이다.


하지만 맨 처음 나오는 Aa라는 단어와 Ba라는 단어는 항상 선택이 강제 되어야하므로 해당 단어와 연결 된 간선들을 모두 제거해준 뒤 그 두단어는 버텍스 커버에 항상 선택된다고 생각한 뒤 문제를 해결하면 된다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
char a[3030];
int n, b[* 26 * 26 + 1], visited[* 26 * 26 + 1], s, e, r;
vector<int> vt[* 26 * 26 + 1];
int cvt(char a, char b) {
    if ('A' <= a&&<= 'Z') {
        int x = a - 'A';
        int y = b - 'a';
        return x * 26 + y + 1;
    }
    else {
        int x = a - 'a';
        int y = b - 'A';
        return x * 26 + y + 26 * 26 + 1;
    }
}
int dfs(int here) {
    if (visited[here])return 0;
    visited[here] = 1;
    for (auto next : vt[here]) {
        if (!b[next] || dfs(b[next])) {
            b[next] = here;
            return 1;
        }
    }
    return 0;
}
int bmatch() {
    int ret = 0;
    for (int i = 1; i <= 26 * 26; i++) {
        memset(visited, 0sizeof(visited));
        if (dfs(i))ret++;
    }
    return ret;
}
int main() {
    scanf("%s"&a);
    for (n; a[n]; n++) {}
    s = cvt(a[0], a[1]);
    e = cvt(a[n - 2], a[n - 1]);
    r += s == e ? 2;
    for (int i = 1; i < n - 1; i ++) {
        int x = cvt(a[i - 1], a[i]);
        int y = cvt(a[i], a[i + 1]);
        if (s != x&&!= y&&!= x&&!= y) {
            vt[x].push_back(y);
            vt[y].push_back(x);
        }
    }
    r += bmatch();
    printf("%d\n", r);
    return 0;
}
cs


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

BOJ)5038 Flight Planning  (0) 2017.07.09
BOJ)8872 빌라봉  (0) 2017.07.08
BOJ)1444 숌 언어  (0) 2017.07.05
BOJ)9023 연습시즌  (0) 2017.06.22
BOJ)13309 트리  (1) 2017.06.21
BOJ)2507 공주 구하기  (0) 2017.06.18
댓글
댓글쓰기 폼