Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:02Z

Repair batch-0002 pages from live compare

← Older revision		Revision as of 00:16, 27 March 2026
Line 2:		Line 2:

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

	== 소스코드 ==		== 소스코드 ==
Line 13:		Line 13:
	private List<String> wordList;		private List<String> wordList;
	private Stack<Integer> stack;		private Stack<Integer> stack;
	private int~~[][]~~ connection;		private int[][] connection;
	private int startingPoint;		private int startingPoint;
	private int longestPassedWordCount;		private int longestPassedWordCount;
Line 41:		Line 41:
	public void makeAdjancencyMatrix() {		public void makeAdjancencyMatrix() {
	int size = wordList.size();		int size = wordList.size();
	connection = new int[size + 1][size + 1];		connection = new int[size + 1][size + 1];

	for(int from = 1; from <= size; from++) {		for(int from = 1; from <= size; from++) {
Line 48:		Line 48:
	String nextWord = wordList.get(to - 1);		String nextWord = wordList.get(to - 1);
	if (isEditStep(word, nextWord)) {		if (isEditStep(word, nextWord)) {
	connection[from][to] = 1;		connection[from][to] = 1;
	if (startingPoint == 0) {		if (startingPoint == 0) {
	startingPoint = from;		startingPoint = from;
Line 90:		Line 90:

	for(int to = from + 1; to <= size; to++) {		for(int to = from + 1; to <= size; to++) {
	if (connection[from][to] == 1) {		if (connection[from][to] == 1) {
	dfs(to);		dfs(to);
	}		}
Line 107:		Line 107:
	}		}

	public static void main(String[] args) {		public static void main(String[] args) {
	EditStepLadders step = new EditStepLadders();		EditStepLadders step = new EditStepLadders();
	while(true) {		while(true) {

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:10Z

New page

2006.1.12

== 접근법 ==
* 입력 단어에 대해 1~n번의 숫자 번호를 붙였다. 행렬[[1...n]][[1...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]]

EditStepLadders/황재선 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

imported>Unknown at 05:23, 7 February 2021