BOJ 18109 - 도깨비불

링크: https://www.acmicpc.net/problem/18109

문제

한글 두벌식 자판으로 타이핑할 때, 다음 글자의 초성 자음이 이전 글자의 받침으로 미리 작성되는 경우를 구하는 문제이다.

자세한 예시는 문제에 자세히 나와있으니 생략한다.

풀이

처음에는 영문 모드로 작성한 아무 문자열이 입력으로 들어오는 줄 알았다.

그래서 모든 케이스에 대해 고려하다보니, 오토마타를 그리게 되었는 데 아래와 같다.
나중에 다시 보니 항상 "완성형 한글"이 입력되는 꼴만 입력되더라... (모음 'ㅏ'키인 k 가 대문자 K로 적히는 경우도 없었다)

여기서 합성모음은 반모음+반모음(ㅘ, ㅝ)와 둘레모음+반모음(ㅞ, ㅙ) 등을 간략히 표현한 것이다. (알맞은 표현을 알려주시면 감사합니다)

화살표에서 겹받침은 ㄳ, ㄼ 등으로 만들어지는 경우를 표시한 것이다.

예시로, ㄱ에 ㅡ(모음)을 붙이면 '그'가 되고, 여기서 다시 ㅣ(그+ㅣ 이므로 합성모음)를 붙이면 '긔'가 된다.

• ø: 아무것도 적히지 않은 빈 상태

• ㄱ, ㄲ: 자음 또는 된자음만 있는 상태

• ㄳ: 겹받침인 상태. 여기서 모음이 붙으면 첫번째 초성은 탈락한다.

• 계, 긔: 초성+중성인 상태. 여기에서 특정 모음들이 다시 붙으면 자음 + 합성모음이 될 수 있다. 예시로 그+ㅣ→긔 가 있다.

• 궁, 궐: 받침이 있는 초성+중성+종성의 상태

• 밟, 없: 받침이 겹받침인 초성+중성+종성의 상태

주의해야할 점은, ㅃ, ㅉ, ㄸ은 받침이 될 수 없다는 점이다.

'도깨비불 현상'이 일어나는 경우는 그림의 빨간색 선으로 움직이는 경우 밖에 없다. 

공집합에서 출발하여, 현재 문자(필요하다면 이전 문자까지)를 확인하여 오토마타대로 따라가다, 빨간색 선만 카운팅하면 된다.

도깨비불 현상이 일어나는 주변을 보면, 상태가 항상 아래의 둘 중 하나이다.

• 모음 + 자음 + 모음

• 모음 + (자음 + 자음) + 모음

위 두 상태만 체크한다면, 코드가 훨씬 간결해진다.

"올곶은 설현네 닭소리 어때"를 영문으로 타이핑한 "dhfrhwdms tjfgussp ekfrthfl djEo"의 답은 3 이다.

코드

편의상 합성모음은 COMBINED_V(combined vowel), 겹받침은 COMBINED_C(combined stop consonant)로 적었다.