[boj : 14748 ] Flow Graph Complexity

https://www.acmicpc.net/problem/14748

14748번: Flow Graph Complexity

저의 1000번째 문제입니다!!!!!!

너무 뿌듯하군요...ㅎㅎ

 

해설 : 2017년 ICPC 문제입니다.

일단 굉장히....어려웠습니다 ㅠㅠㅠ 언뜻 보기엔 단순히 파싱문제처럼 보이지만 마구잡이로 파싱을 해서 풀 수 있는 문제는 아니더라구요... 정의가 굉장히 중요한 문제입니다.

 

문제 해설부터 하면, 하나의 그래프가 주어집니다. 이때 각 노드의 symbol 은 S,L,B 이 세 문자 중에 하나를 갖습니다.

 

S : 가장 기본 심볼입니다. 전진 간선을 갖습니다.(단, 마지막에 S가 위치한다면 전진 간선은 존재하지 않습니다.)

L : 루프 심볼입니다. 루프 심볼은 자신의 statement 가 종료된 노드서부터 후진 간선이 존재하고, 자신으로 부터 statement 가 종료된 이후에 전진 간선이 존재합니다.

B : 브랜치 심볼입니다. 브랜치 심볼은 자신의 statement가 종료된 노드로 전진 간선이 존재합니다.

 

위의 내용은 간단히 이해만 하면 되고, 중요한건 이를 수치화 하는 것 입니다.

 

S : 정점 1개와 전진 간선1개가 하나씩 추가 됩니다.

L : 정점 2개와 전진 간선 2개와 후진 간선 1개가 추가됩니다.

B : 정점 2개와 전진 간선 2개가 추가됩니다.

 

이를 바탕으로 E(f),E(b),V를 구해보면

 

V = S의 개수 + L의 개수 + B의 개수

E(f) = V + B의 개수 -1 ( 마지막에 S는 전진 간선이 없기때문)

E(b) = L 의 개수

 

이렇게 정의가 가능합니다.

그러면 이제 invaild 한 경우의 수만 잘 제거하면 될텐데,,,,이게 만만하지 않습니다.

 

1)  the parentheses and the brackets are unmatched : 괄호의 쌍이 매칭이 안되거나

2)  it contains punctuation symbols other than parentheses, brackets, and commas : 소괄호,대괄호, 컴마(,) 가 아니거나

3) the punctuation symbols are added or omitted wrongly such as S,,S, SS, or B,(S), : 심볼이 형식적이지 못하게 추가되거나 제거될때

4) it contains unknown types of node other than S, L, or B : 심볼 S,L,B 가 아닌 문자가 들어올때

 

우린 이를 invaild 라고 판단해 줄겁니다.

그러나 이를 하나씩 손으로 걸러주기엔 정말 너무 많은 케이스들을 제거해나아가야 되기때문에 너무 힘들어요 ㅠㅠㅠ

 

그래서 우린 이에 대한 문법을 정의해 볼겁니다.(djm03178님 감사합니다)

즉, 오토마타 수업때 배웠던 문법을 적용해 볼겁니다.

 

만약 시작 심볼을 X라고 한다면,

 

X -> S | S,X

S -> L(X) | L[X] | B(X) | B[X]

 

라고 정의를 할 수 있습니다. 근데 이게 한번에 구하기에는 너무 힘들어요 ㅠㅠㅠ

그래서 각 문자가 위치해 있을때 이 문자에 대해 앞뒤 문자를 확인해 보는거에요.

 

(1) S

(2) L,B

(3) (,[

(4) ),]

(5) ,

 

이렇게 말이죠.

(1) : S가 위치할 수 있는 위치는 어디나 가능합니다.

S뒤에 위치할 수 있는 심볼은 ',' , ')', ']' 

 

(2) : L,B가 위치할 수 있는 위치는 맨 마지막 빼고는 다 가능합니다.

L 뒤에 위치할 수 있는 심볼 : ')' , ']'

 

(3) : ( , [ 가 위치할 수 있는 위치는 맨 앞과 맨 마지막 빼고는 다 가능합니다.

( , [ 뒤에 위치할 수 있는 심볼 : 'S' , 'L' , 'B'

 

(4) : ) , ] 가 위치할 수 있는 위치는 맨 앞 빼고는 다 가능합니다.

) , ] 뒤에 위치할 수 있는 심볼 : ',' , ')' , ']'

 

(5) : , 위 위치할 수 있는 위치는 맨 앞과 맨 뒤 빼고는 다 가능합니다.

, 뒤에 위치할 수 있는 심볼 : 'S' , 'L' , 'B'

 

그리고 위의 케이스에 속하지 않는다면 이는 invaild 하다는 뜻입니다.

 

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int w;
	string str;
	
	cin >> w;
	
	cin.ignore();
	getline(cin, str);
	str.erase(remove(str.begin(), str.end(), ' '), str.end());
	
	int l = 0, b = 0, v = 0;
	stack<char> st;

	int ans=0;
	if (str.length() <= 0) {
		cout << -1;
		return 0;
	}
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'S') {
			if (i+1<str.length() && str[i+1] != ',' && str[i + 1] != ')' && str[i + 1] != ']') {
				ans = -1;
				break;
			}
			v++;
		}
		else if (str[i] == 'B' || str[i] == 'L') {
			if (i==str.length()-1 || (str[i + 1] != '(' && str[i + 1] != '[')) {
				ans = -1;
				break;
			}
			if(str[i]=='L')
				v++, l++;
			else
				v++, b++;
		}
		else if (str[i] == '(' || str[i] == '[') {
			if (i==0 || i==str.length()-1 || (str[i + 1] != 'S' && str[i + 1] != 'L' && str[i + 1] != 'B')) {
				ans = -1;
				break;
			}
			st.push(str[i]);
		}
		else if (str[i] == ',') {
			if (i==0 || i == str.length() - 1 || (str[i + 1] != 'S' && str[i + 1] != 'L' && str[i + 1] != 'B')) {
				ans = -1;
				break;
			}
		}
		else if (str[i] == ')' || str[i] == ']') {
			if (i==0 || (i+1<str.length() && str[i + 1] != ',' && str[i + 1] != ')' && str[i + 1] != ']')) {
				ans = -1;
				break;
			}
			if (!st.empty()) {
				if ((st.top() == '(' && str[i] != ')') || (st.top() == '[' && str[i] != ']')) {
					ans = -1;
					break;
				}
				st.pop();
			}
			else {
				ans = -1;
				break;
			}
		}
		else {
			ans = -1;
			break;
		}
	}
	if (!st.empty())ans = -1;
	if (ans == -1) {
		cout << ans;
		return 0;
	}
	v += (l + b);
	int ef = v + b - 1;
	int eb = l;
	
	cout<<  ef + (w * eb) - v + 2;
	return 0;
}