(JAVA) 백준 1013번 : Contact --- [문자열 - 오토마타]

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

1013번: Contact

 

안녕하세요.

 

 

이 문제는 단순 문자열 문제가 아니라

 

정규표현식 문제이다.

 

 

자바의 정규표현식 기능을 사용해도 되긴 하지만,

 

자바 정규표현식 기능을 사용하는 것보다

 

오토마타 전이 그래프(DFA라고 하죠) 를 직접 그려보는 것 + 오토마타 상태 그래프를 바탕으로 알고리즘을 짜서 코딩하는 것

 

이 훨씬 빠르고 도움이 된다고 생각되서 이렇게 수행했다.

 

 

처음에는 단순히 하나씩 계산하려고 애먹었지만, 검색 한번으로 오토마타를 보니 감이 확 왔었다..

 

 

 

그래서 처음 시작 전 상태를 0으로 놓고,

 

parameter로 state와 현재 문자 를 받아오는 함수를 구현해

 

거기 내부에서 switch와 if절로 오토마타 다음 상태를 구현했다.

 

 

 

그렇게 문자하나하나 따져가며 전체 문자열을 한 번 순회한 후

 

현재 상태가 종료 상태인지 체크해서 YES or NO 를 판가름했다.

 

 

아래는 오토마타 전이 그래프(DFA) 를 직접 그려보았다.

 

필자가 직접 그렸다... 죄송합니다.

  -  동그라미 안의 숫자는 State(상태)

  -  화살표 위의 숫자는 입력 문자(0 또는 1)

 

 

 

 

나머지 매커니즘은 하단 소스코드를 참고하시면 됩니다.

 

감사합니다!

 

 

 

 

 

소스코드

---