[백준] 1444 숌 언어

문제 주소 : www.acmicpc.net/problem/1444

1444번: 숌 언어

문제 확인

 

최소 버텍스 커버 문제입니다.

처음과 끝 단어는 꼭 포함시켜야 하며 현재 위치 기준으로 양 옆의 문자를 버텍스로 두어 이분매칭 그래프를 작성하면 됩니다.

 

풀이

 

2개의 문자를 버텍스로 두고 Aa, aA를 구분하기 위해 배열의 크기를 26 * 26 * 2로 둡니다.

아스키 수를 비교하는 것 보다 isupper 함수를 이용하는 것이 더 빠르므로 이 함수를 사용합니다.

이미 포함된 처음, 끝 단어를 빼고 그래프를 작성한 후 최소 버텍스 커버 알고리즘을 적용하면 풀립니다.

최소 버텍스 커버 : latter2005.tistory.com/37

[백준] 1867 돌멩이 제거

 

코드

#include <cstdio>
#include <cstring>
#include <vector>
#include <ctype.h>
using namespace std;
vector<int> graph[1353];
int match[1353];
bool visit[1353];
inline int index(char a, char b) {
    if (isupper(a))
        return (a-'A') * 26 + (b-'a') + 1;
    return (a - 'a') * 26 + (b - 'A') + 677;
}
int dfs(int i) {
    if (visit[i])return 0;
    visit[i] = 1;
    for(auto next : graph[i])
        if (!match[next] || dfs(match[next])) {
            match[next] = i;
            return 1;
        }
    return 0;
}
int main() {
    int n, res, start, end;
    char ary[3031];
    scanf("%s", ary);
    n = strlen(ary);
    
    start = index(ary[0], ary[1]);
    end = index(ary[n - 2], ary[n - 1]);
    
    res = (ary[0] != ary[n - 2] || ary[1] != ary[n - 1]) ? 2 : 1;
    for (int i = 1; i < n - 1; i++) {
        int x = index(ary[i - 1], ary[i]);
        int y = index(ary[i], ary[i + 1]);
        if (start != x && start != y && end != x && end != y) {
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
    }
    for (int i = 1; i < 677; i++) {
        memset(visit, 0, sizeof(visit));
        if (dfs(i))res++;
    }
    printf("%d", res);
}