취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1013번 문제인 Contact이다.
문제는 아래 링크를 확인하자.

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

주어진 표현 (100+1+|01)+ 을 결정적 유한 오토마타(DFA, Deterministic Finite Automata)로 나타내 문제를 해결해보자.

아래는 글쓴이의 코드에 구현된 DFA의 로직이다.

"노드0"을 불가능한 노드를 의미하는 노드로 사용하자. 그리고 아무 것도 쓰지 않은 첫 상태를 노드1이라 하자.

노드1 상태에서 0을 쓴다면 "01"의 "0"을 채운 상태(노드2)가 되고, 1을 쓴다면 "100+1+"의 "1"을 채운 상태(노드3)이 된다.

노드2 상태에서 0을 쓴다면 주어진 형태의 문자열이 될 수 없으므로 노드0 상태가 되고, 1을 쓴다면 다시 새로운 시작을 기다리는 처음상태(노드1)이 된다.

노드3 상태에서 0을 쓴다면 "100+1+"의 "10"을 채운 상태(노드4)가 되고, 1을 쓴다면 주어진 형태의 문자열이 될 수 없으므로 노드0 상태가 된다.

노드4 상태에서 0을 쓴다면 "100+1+"의 "100+"을 채운 상태(노드5)가 되고, 1을 쓴다면 주어진 형태의 문자열이 될 수 없으므로 노드0 상태가 된다.

노드5 상태에서 0을 쓴다면 "100+1+"의 "100+"을 채운 상태(노드5)가 되고, 1을 쓴다면 "100+1+"의 마지막 1을 막 처음 채운 상태(노드6)가 된다.

노드6 상태에서 0을 쓴다면 이는 새로운 시작을 하여 "01"의 "0"을 채운 상태(노드2)가 되고, 1을 쓴다면 "100+1+"의 마지막 1의 반복에 해당되거나 새로운 시작의 "100+1+"의 첫 1을 담당할 수 있는 1이 현재의 마지막에 있는 상태(노드7)가 된다.

노드7 상태에서 0을 쓴다면 새로운 시작의 "100+1+"의 "10" 또는 새로운 시작의 "01"의 "0"을 담당하는 0을 적은 상태(노드8)가 되고, 1을 쓴다면 "100+1+"의 마지막 1의 반복에 해당되거나 새로운 시작의 "100+1+"의 첫 1을 담당할 수 있는 1이 현재의 마지막에 있는 상태(노드7)가 된다.

노드8 상태에서 0을 쓴다면 새로운 시작의 "100+1+"의 "100+"을 작성한 상태(노드5)가 되고, 1을 쓴다면 새로운 시작의 "01"의 "01"을 채우고 새로운 시작을 기다리는 처음 상태(노드1)가 된다.

위와 같은 DFA를 구현해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int DFA[9][2];
bool chk[9];

void solve() {
	int cur = 1;
	string s; cin >> s;
	for (auto l : s) {
		cur = DFA[cur][l - '0'];
	}
	if (chk[cur]) cout << "YES\n";
	else cout << "NO\n";
}

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

	DFA[1][0] = 2, DFA[1][1] = 3;
	DFA[2][0] = 0, DFA[2][1] = 1;
	DFA[3][0] = 4, DFA[3][1] = 0;
	DFA[4][0] = 5, DFA[4][1] = 0;
	DFA[5][0] = 5, DFA[5][1] = 6;
	DFA[6][0] = 2, DFA[6][1] = 7;
	DFA[7][0] = 8, DFA[7][1] = 7;
	DFA[8][0] = 5, DFA[8][1] = 1;
	chk[1] = chk[6] = chk[7] = 1;

	int T; cin >> T;
	while (T--) {
		solve();
	}
}