EditStepLadders/황재선

2006.1.12

접근법

• 입력 단어에 대해 1~n번의 숫자 번호를 붙였다. 행렬1...n1...n에 편집 단계인 단어에 대해 값을 주어서 방향 그래프를 만들었다. 예를 들어, 1번과 2번 단어가 편집단어라면 mat[1][2] = 1 아니면 0값을 주었다. 가장 depth가 긴 path에 있는 vertex의 개수를 출력하면 된다.

소스코드

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

---

EditStepLadders