2006.1.13
== 쓰레드 ==
 * Sample Input은 동작하는데 모든 경우에 되는지는 모르겠다.. 채점 사이트가 SE5.0을 지원하면 올려봐야지..
 * Graph 이용. 시작 단어에서 끝 단어의 path 검색은 dfs로 구현.

== 소스 코드 ==
{{{~java
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class DoubletsSimulator {
	private List<String> wordList;
	private Stack<String> solutionStack;
	private Stack<String> stack;
	private int minWordCount;
	private int start;
	private int end;
	private int[][] doublet;
	
	
	public DoubletsSimulator() {
		wordList = new ArrayList<String>();
		stack = new Stack<String>();
		solutionStack = new Stack<String>();
		minWordCount = Integer.MAX_VALUE;
	}
	
	public String readWord() {
		try {
			return new Scanner(System.in).useDelimiter("\n").next().trim();	
		}
		catch(Exception e) {
			return null;
		}
	}

	public boolean isDoublet(String word1, String word2) {
		if (word1.length() != word2.length()) {
			return false;
		}
		
		Scanner sc1 = new Scanner(word1).useDelimiter("");
		Scanner sc2 = new Scanner(word2).useDelimiter("");
		
		int differentBitCount = 0;
		while(sc1.hasNext()) {
			if (!sc1.next().equals(sc2.next())) {
				differentBitCount++;
			}
		}

		return differentBitCount == 1 ? true : false;
	}
	
	public void storeWord(String word) {
		wordList.add(word);		
	}

	
	public void makeDoubletMatrix() {
		int n = wordList.size();
		doublet = new int[n + 1][n + 1];
		
		for(int from = 1; from <= n; from++) {
			String source = wordList.get(from - 1);
			for(int to = from + 1; to <= n; to++) {
				String destination = wordList.get(to - 1);
				if (isDoublet(source, destination)) {
					doublet[from][to] = 1;
					doublet[to][from] = 1;
				}
			}
		}
	}
	
	public void setEndToEnd(String word1, String word2) {
		start = wordList.indexOf(word1) + 1;
		end = wordList.indexOf(word2) + 1;
	}
	
	public void dfs(int from) {
		stack.add(wordList.get(from - 1));
		String destination = wordList.get(end - 1);
		if (stack.peek().equals(destination)) {			
			int stackWordCount = stack.size();
			if (stackWordCount < minWordCount) {
				solutionStack = (Stack) stack.clone();
				minWordCount = stackWordCount;
			}
		}
		else {
			int size = wordList.size();
			for(int to = 1; to <= size; to++) {
				// Stack의  위에서 2번째 값(String)의 item번호가 to와 같으면
				// (바로 전에 거쳤던 곳) continue 
				if (to == wordList.indexOf(stack.get(stack.size() >= 2?
						stack.size() - 2 : 0)) + 1) {
					continue;
				}
				if (doublet[from][to] == 1) {
					dfs(to);
				}
			}
		}
		stack.pop();
	}
	
	public void printResult() {
		if (solutionStack.isEmpty()) {
			System.out.println("No solution.");
		}
		else {			
			Iterator it = solutionStack.iterator();
			while(it.hasNext()) {
				System.out.println((String) it.next());
			}
			solutionStack.clear();
		}
	}
	
	public int getStartingPoint() {
		return start;
	}
	public static void main(String[] args) {
		DoubletsSimulator simulator = new DoubletsSimulator();
		
		while(true) {
			String word = simulator.readWord();			
			if (word.equals("")) {
				break;
			}
			simulator.storeWord(word);
		}
		
		simulator.makeDoubletMatrix();
		while(true) {
			String words = simulator.readWord();			
			if (words == null || words.equals("")) {
				break;
			}
			simulator.setEndToEnd(words.split(" ")[0], words.split(" ")[1]);
			simulator.dfs(simulator.getStartingPoint());
			simulator.printResult();
		}
	}
}
}}}
----
[Doublets]