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(); } } }