알고리듬 코딩 이벤트 마지막 문제 풀이입니다.
사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.
###실행 예
input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE
###사전 데이터
네 글자 단어 - word4
다섯 글자 단어 - word5
###심화 문제 - 풀지 않아도 됩니다
심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.
심화문제 2: 최대한 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.
이 문제는 그래프를 탐색해서 두 노드간의 경로를 찾는 문제 같습니다.
먼저 파일에서 사전을 읽어서 그래프를 만들기로 했습니다.
WordGraphBuilder가 그래프를 그리는 역할을 합니다. 테스트를 쉽게 하려 사전 내용 WordGraphBuilder.WordSource 인터페이스를 구현한 개체를 통해 얻도록 했습니다. ReaderWordSource는 java.util.Reader를 통해 읽기 때문에 파일 시스템의 파일이나 클래스 경로 상의 자원에서 사전을 읽는데 사용됩니다. 테스트에서는 배열에서 읽도록 했습니다.
저는 두가지 탐색 방식을 구현했습니다. 하나는 비교적 짧은 경로라고 추정되는 경로를 단어의 유사성을 비용으로 취급해 찾아내는 방식이고 또 하나는 모든 경로를 검토해 최단 거리를 찾아내는 방식입니다.
탐색알고리즘은 PathFinder란 인터페이스를 구현해야 합니다.
최장 거리 탐색은 NP인지라 Fork&Join으로 병렬처리하는 방식으로 풀어볼 생각이지만 무식한(Brute Force) 방법이라 굳이 구현할 필요가 있나 싶네요. 다만 비용 추정 탐색을 거꾸로 해서 목적 단어와 비슷하지 않은 단어를 우선 선택하다 보면 휴리스틱하게 먼 경로를 찾을 수 있지 않을까 싶습니다.
이 그래프에는 비용이라고 할만한 부분이 없어서 순차적으로 탐색해야하지만, 지금 위치한 단어와 유사한(문자가 하나만 다른) 단어 중에서도 목적지 단어에 포함된 문자가 있는 단어를 선택하면 그나마 빠른 길을 찾을 수 있을 거란 약한 추정을 근거로 해서 탐색을 합니다.
모든 경로를 뒤져서 가장 짧은 경로를 찾습니다. 메모리를 절약하려고 깊이 우선 탐색 방법을 사용하되 "비용 추전 탐색"을 먼저 해 본 이후에 그 결과를 바탕으로 더 깊은 경로를 배제한 상태에서 탐색하기 때문에 그리 오래 걸리지 않습니다.
비용 추정 경로는 다음과 같이 실행합니다.
$java org/fupfin/insight/evnet2b/Runner org/fupfin/insight/evnet2b/word4.dic ably zain
Run time: 0.124 secs
1:ABLY
2:ABAY
3:AWAY
4:AWNY
5:AWRY
6:ADRY
7:AERY
8:AERO
9:ZERO
10:CERO
11:MERO
12:HERO
13:HERN
14:DERN
15:DARN
16:BARN
17:BAIN
18:ZAIN
최단 거리 경로는 -s 옵션을 줘서 실행합니다.
$java org/fupfin/insight/evnet2b/Runner -s org/fupfin/insight/evnet2b/word4.dic ably zain
Run time: 2.883 secs
1:ABLY
2:ABAY
3:AWAY
4:SWAY
5:SWAN
6:SAAN
7:SAIN
8:ZAIN