2012/09/13 15:37

코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이

  <- 이 책에 나오는 문제라고 합니다.

문제 출처는 다음 링크입니다.
http://www.insightbook.co.kr/post/3917 

『코딩 인터뷰 완전 분석』215쪽 고난이도 연습문제 18.10

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

[실행 예]

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

[사전 데이터]

네 글자 단어 - word4

다섯 글자 단어 - word5

 

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

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

 이 문제는 사전상의 각 단어를 노드, 변환가능한 단어쌍을 링크로 놓으면 그래프에서의 경로찾기 문제로 치환할 수 있습니다.  

여기서는 A* 알고리즘을 써서 구현했습니다. A*알고리즘에서는 현재 위치가 목표와 얼마나 가까운지 예측하는 게 필요한데, 글자 하나 다를 때 한 번만에 옮겨갈 수 있다고 보수적인 추정을 사용하면 시간을 약간 더 걸리지만 최소 경로를 찾아낼 수 있습니다. 

최대 경로, 즉 가장 많은 수의 단어를 쓰는 경우는 변환을 한 번 할 때 weight을 -1로 둬서 가장 많은 변환을 하도록 해 주면 찾을 수 있습니다. 

 실행결과:

(damp -> like):(5)[damp, dame, dime, dike, like]

(start -> final):(13)[start, stare, stave, seave, serve, serie, ferie, ferae, feral, fetal, fatal, fanal, final]

(china -> japan):(15)[china, chine, shine, seine, seise, sense, mense, manse, manie, matie, matin, satin, satan, sapan, japan]

(damp -> like):(2734)[]  <-- 결과는 longest.txt 에 올려놨습니다.

찾아보니 다른 분이 더 긴 longest 결과를 찾으셨네요 ^^; 제 건 부정확한 듯. 좀 더 고쳐보겠습니다. 


package insightbook.event.last;

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.FileSystem;
import java.nio.file.FileSystems;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Set;

public class WordTransform {

private final Map<String, Collection<String>> link;

private WordTransform(Map<String, Collection<String>> link) {
this.link = link;
}

public static Builder getBuilder() {
return new Builder();
}

public Collection<String> getTransformableWords(String word) {
return link.get(word);
}


public List<String> findPath(String start, String goal) {
return findPath(start, goal, 1);
}

public List<String> findLongestPath(String start, String goal) {
return findPath(start, goal, -1);
}

public List<String> findPath(String start, String goal, int weightPerTransform) {

// Cost from start along best known path.
final Map<String, Integer> gScore = new HashMap<>();
gScore.put(start, 0);

// Estimated total cost from start to goal through y.
final Map<String, Integer> fScore = new HashMap<>();
fScore.put(start, huristicCostEstimate(start, goal, weightPerTransform));

// The set of nodes already evaluated.
Set<String> closedSet = new HashSet<>();

// The set of tentative nodes to be evaluated,
// initially containing the start node
Set<String> openSet = new HashSet<>();
openSet.add(start);

// Priority Queue for picking up least fScore
final int INITIAL_CAPACITY = 11;
PriorityQueue<String> queue = new PriorityQueue<String>(
INITIAL_CAPACITY, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
int diff = fScore.get(o1) - fScore.get(o2);
return (diff!=0)? diff : o1.compareTo(o2);
}
});
queue.add(start);

// The map of navigated nodes.
Map<String, String> cameFrom = new HashMap<>();

while (!queue.isEmpty()) {
String current = queue.poll();
openSet.remove(current);
// System.out.println(fScore.get(current)+":"+constructPath(cameFrom, current));
if (goal.equals(current)) {
// System.out.println("count: "+closedSet.size());
return constructPath(cameFrom, current);
}
closedSet.add(current);

int tentativeGScore = gScore.get(current) + weightPerTransform;
Collection<String> ns = getTransformableWords(current);
if (ns==null) continue;
for (String neighbor : ns) {
if (closedSet.contains(neighbor))
continue;
if (!openSet.contains(neighbor)
|| tentativeGScore < gScore.get(neighbor)) {

cameFrom.put(neighbor, current);
gScore.put(neighbor, tentativeGScore);
fScore.put(neighbor, gScore.get(neighbor)
+ huristicCostEstimate(neighbor, goal, weightPerTransform));

if (!openSet.contains(neighbor))
openSet.add(neighbor);
queue.add(neighbor);
}
}
}

return null;
}

private List<String> constructPath(Map<String, String> cameFrom, String current) {

List<String> path = (cameFrom.containsKey(current)) ?
constructPath(cameFrom, cameFrom.get(current)) : new LinkedList<String>();
path.add(current);
return path;
}

private int huristicCostEstimate(String start, String goal, int multiplyCoeff) {

int estimate = 0;

for (int i = 0; i < Math.min(start.length(), goal.length()); i++) {
if (start.charAt(i) != goal.charAt(i))
estimate++;
}

return estimate * multiplyCoeff;
}

static String[] getMasks(String s) {

String[] masks = new String[s.length()];
for (int i = 0; i < s.length(); i++) {
masks[i] = s.substring(0, i) + "*" + s.substring(i + 1, s.length());
}

return masks;
}

public static class Builder {

private Map<String, Set<String>> maskSet = new HashMap<>();

public Builder load(String word) {

String[] masks = getMasks(word);
for (String mask : masks) {
if (!maskSet.containsKey(mask))
maskSet.put(mask, new HashSet<String>());
maskSet.get(mask).add(word);
}

return this;
}

public Builder load(Path path) {
try (BufferedReader reader = Files.newBufferedReader(path,
StandardCharsets.UTF_8);) {

for (String line = reader.readLine(); line != null; line = reader
.readLine()) {
load(line);
}

} catch (IOException e) {
e.printStackTrace();
}
return this;
}

public WordTransform build() {

Map<String, Collection<String>> link = new HashMap<>();

for (Entry<String, Set<String>> e : maskSet.entrySet()) {
if (e.getValue().size() > 1) {
Set<String> set = e.getValue();
for (String word : set) {
if (!link.containsKey(word))
link.put(word, new HashSet<String>());
link.get(word).addAll(getRelativeComplement(word, set));
}
}
}

return new WordTransform(link);
}

private static Collection<? extends String> getRelativeComplement(
String word, Set<String> set) {
Set<String> rc = new HashSet<>(set);
rc.remove(word);
return rc;
}

}

public void printPath(String start, String goal) {

List<String> path = findPath(start, goal);
System.out.printf("(%s -> %s):(%d)%s\n", start, goal, (path==null)?-1:path.size(), path);
}

public void printLongestPath(String start, String goal) {

List<String> path = findLongestPath(start, goal);
System.out.printf("(%s -> %s):(%d)%s\n", start, goal, (path==null)?-1:path.size(), path);
}

public static void main(String[] args) {

FileSystem fs = FileSystems.getDefault();
Path path4 = fs.getPath("word4.txt");
Path path5 = fs.getPath("word5.txt");
WordTransform t = WordTransform.getBuilder().load(path4).load(path5).build();

t.printPath("damp", "like");
t.printPath("start", "final");
t.printPath("china", "japan");

t.printLongestPath("damp", "like");
}

}

덧글

  • 히언 2012/09/19 17:19 # 답글

    오, 역시 머리쓰기의 달인이셨군요!!!
  • 성큼이 2012/09/20 23:25 #

    ㅋㅋ 달인은 좀 많이 아닌 것 같지만 퍼즐풀이 같은건 즐기는 편입죠 ^^;
  • 앙탈 2012/11/04 19:50 # 답글

    성큼형님 저 한달남았어여 ㅠㅠ

    잘지내시나여
  • 성큼이 2012/11/08 14:17 #

    ㅎㅎ 잘 지내요 몸조심하고 무사히 전역해요
댓글 입력 영역