사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.

[실행 예]

input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

[사전 데이터]

네 글자 단어 - word4

다섯 글자 단어 - word5

[심화 문제 - 풀지 않아도 됩니다]

심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.
심화문제 2: 최대한 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.


풀이:

심화문제 1번은 단순한 shortest path 문제이며, A* search를 이용하면 쉽게 풀립니다. 그러나 심화문제 2번은 Hamiltonian path 문제로, 유명한 NP-hard 문제이므로 그냥 스킵했습니다.

코드는 여기

Glasgow Haskell Compiler 7.2.1로 컴파일했으며, 표준 라이브러리만을 사용했습니다.

$> ./search 

input: store, fight

output: store -> stoke -> stuke -> souke -> souse -> rouse -> roust -> rouet -> roset -> reset -> beset -> beget -> begot -> bigot -> bight -> fight

$> ./search 

input: damp, like

output: damp -> dame -> dime -> dike -> like

신고

티스토리 툴바