2006.1.12
접근법 ¶
소스코드 ¶
~java import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.Stack; public class EditStepLadders { private List<String> wordList; private Stack<Integer> stack; private int[][] connection; private int startingPoint; private int longestPassedWordCount; public EditStepLadders() { wordList = new ArrayList<String>(); stack = new Stack<Integer>(); } public String readWord() { try { return new Scanner(System.in).nextLine(); } catch (Exception e) { return null; } } public void storeWord(String word) { wordList.add(word); } public boolean isExistWord() { return !wordList.isEmpty(); } public void makeAdjancencyMatrix() { int size = wordList.size(); connection = new int[size + 1][size + 1]; for(int from = 1; from <= size; from++) { String word = wordList.get(from - 1); for(int to = from + 1; to <= size; to++) { String nextWord = wordList.get(to - 1); if (isEditStep(word, nextWord)) { connection[from][to] = 1; if (startingPoint == 0) { startingPoint = from; } } } } } public boolean isEditStep(String word1, String word2) { int length1 = word1.length(); int length2 = word2.length(); int lengthGap = Math.abs(length1 - length2); if (lengthGap < 0 || lengthGap > 1) { return false; } int minLength = Math.min(length1, length2); Scanner sc1 = new Scanner(word1).useDelimiter(""); Scanner sc2 = new Scanner(word2).useDelimiter(""); int differentBit = 0; for(int i = 0; i < minLength; i++) { if (!sc1.next().equals(sc2.next())) { differentBit++; } } if (lengthGap == 0) { return differentBit == 1 ? true : false; } else { return differentBit == 0 ? true : false; } } public void dfs(int from) { int size = wordList.size(); stack.add(from); for(int to = from + 1; to <= size; to++) { if (connection[from][to] == 1) { dfs(to); } } longestPassedWordCount = Math.max(longestPassedWordCount, stack.size()); stack.pop(); } public int getStartingPoint() { return startingPoint; } public void printResult() { System.out.println(longestPassedWordCount); } public static void main(String[] args) { EditStepLadders step = new EditStepLadders(); while(true) { String word = step.readWord(); if (word == null || word.equals("")) { break; } step.storeWord(word); } if (step.isExistWord()) { step.makeAdjancencyMatrix(); step.dfs(step.getStartingPoint()); step.printResult(); } } }