BOJ)14748 Flow Graph Complexity

문제: icpc.me/14748

주어진 문자열로 만들 수 있는 그래프의 C값을 구하는 문제이다.

C값은 EF+W*EB-V+2 로 구할 수 있다.

즉 주어진 문자열을 잘 파싱하여서 EF, EB, V 세 값을 구해내면 되는 문제이다.

하지만 문제에서 valid하지 않은 경우가 주어지는데 이는 일단 생각하지 말고 주어진 조건에 따라서 그래프를 그리게 된다면

EB가 생기는 경우는 무조건 L이 있는 경우이다 즉, EB의 수는 L이 등장하는 횟수이다.

V가 생기는 경우는 S일 때는 하나가 생기며, L이나 B의 경우 하나가 더 생겨서 2개가 생긴다.

즉 V의 수는 S+2*L+2*B 이다.

마지막으로 EF의 수는 각 정점은 마지막 정점을 제외하고 모두 아래로 하나씩 EF를 쏜다. (L에 의하여 생기는 정점은 간선을 받지 않지만 잘 생각해보면 l에서 간선을 두번 쏘기 때문에 상쇄된다.) 

그러므로 EF의 수는 V-1인데 이 때, B정점의 경우 하나의 간선을 더 쏘기 때문에 B의 개수만큼 더해진다

즉 EF의 수는 V-1+B 가 된다.

만약 valid하다면 저 값들을 이용하여 구한 답을 출력하면 되고, valid하지 않다면 -1을 출력하면 된다.

valid하지 않은 조건을 검사하는건 조건에 맞게 적절히 해주면 된다.... (?) 괄호의 경우는 stack을 이용하면 효율적으로 확인해줄 수 있다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
using namespace std;
string in, s;
stack<char> st;
int w, sc, l, b;
void invalid() {
    puts("-1");
    exit(0);
}
int main() {
    scanf("%d", &w);
    getchar();
    getline(cin, in);
    string s = "";
    int inlen = in.length();
    for (int i = 0; i < inlen; i++)
        if (in[i] != ' ')
            s += in[i];
    int len = s.length();
    for (int i = 0; i < len; i++) {
        if (s[i] == 'S' || s[i] == 'L' || s[i] == 'B') {
            if (i && (s[i - 1] == ')' || s[i - 1] == ']' || s[i - 1] == 'S' || s[i - 1] == 'L' || s[i - 1] == 'B'))
                invalid();
            if (s[i] == 'S')
                sc++;
            else if (s[i] == 'L')
                l++;
            else
                b++;
            if (s[i] != 'S') {
                if (i != len - 1 && s[i + 1] != '('&&s[i + 1] != '[')
                    invalid();
            }
        }
        else if (s[i] == '(' || s[i] == '[') {
            if (i&&s[i - 1] != 'L'&&s[i - 1] != 'B')
                invalid();
            st.push(s[i]);
        }
        else if (s[i] == ')' || s[i] == ']') {
            if (i&&s[i - 1] != 'S'&&s[i - 1] != ')'&&s[i - 1] != ']')
                invalid();
            if (s[i] == ')') {
                if (st.size() && st.top() == '(')
                    st.pop();
                else
                    invalid();
            }
            else {
                if (st.size() && st.top() == '[')
                    st.pop();
                else
                    invalid();
            }
        }
        else if (s[i] == ',') {
            if (i&&s[i - 1] != ']'&&s[i - 1] != ')'&&s[i - 1] != 'S')
                invalid();
            continue;
        }
        else
            invalid();
    }
    if (st.size())
        invalid();
    if (s[0] != 'S'&&s[0] != 'L'&&s[0] != 'B')
        invalid();
    if (s[len - 1] != ')'&&s[len - 1] != ']'&&s[len - 1] != 'S')
        invalid();
    int v = sc + 2 * l + 2 * b;
    int ef = b + v - 1;
    int eb = l;
    printf("%d\n", ef + w*eb - v + 2);
    return 0;
}