[Algorithm] 백준 1013번 Contact
#Finite State Machine #BFS #Graph #Algorithm #Python #Regex
본 문제는 Regular Expression(Regex), 정규식 문제로 분류할 수 있다.
문제를 요약하면 주어진 문자열 입력이 정규식 (100+1+ | 01)+ 을 통해 만들어질 수 있는지 YES 혹은 NO로 출력하는 것 이다.
파이썬에서 정규식 관련내장 라이브러리 함수를 이용해 1~2줄로 문제를 풀 수 있었지만 기존에 정규식 함수가 있는지 몰랐기 때문에 Finite State Machine을 파이썬으로 구현함으로써 순수하게 풀었다. Finite State Machine 의 state를 그래프의 각 노드로 만듦으로써 그래프화 하고 BFS를 통해 다음 상태로 전이하는 방식으로 문제에 접근했다. 또한 노드의 탐색을 위해서 Deque를 사용했다.
이것을 풀기 위해 (100+1+ | 01)+ 의 해당 자리의 수 별로 state를 설정했고 여태 입력 된 것을 토대로 state가 변화되도록 했다.
그리고 각 state 별로 각각 0/1 때 갈 수 있는 경로를 미리 정해놓고 입력에 따라 그 경로를 탐색하도록 했다.
초록색은 01로 끝나는 경우인데 어차피 01이 되는 순간 새롭게 시작하는 위치에서 시작하는 것과 동일하므로 6까지 가는 경로는 살필 필요가 없다.
빨간색은 입력이 1일 때 갈 수 있는 경로, 파란색은 입력이 0일 때 갈 수 있는 경로이다. 예를 들어서 주어진 입력 값이 100001 이라고 하면 1은 빨간선, 0은 파란선을 따라가면 변화하는 state는 100001에 따라 아래와 같이 변하게 된다.
이 때, 주어진 문자열인 100001이 종료 되는 시점에 state가 0이라면 주어진 문자 정규식에 문자열인 것 이다. 따라서 위와 같은 그래프를 BFS로 탐색해주고 맨 마지막 인덱스까지 살아남는 route가 있고 그 route의 종착 state 가 0인 것이 있다면 주어진 정규식에 합당한 것 이다.
같은 방법으로 10010111을 살펴보면 다음과 같이 맨 마지막 index까지 오는 route가 존재하지 않는다. 그렇기 때문에 정규식이 될 수 없다.
이를 코드로 구현하면
참고 : 이번 기회에 파이썬 정규식에 대해서 공부했다. 파이썬에서 정규식에 대해 공부했었다면 제공되는 함수로 쉽게 풀 수 있던 문제였다.