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 17:		Line 17:
	private int start;		private int start;
	private int end;		private int end;
	private int~~[][]~~ doublet;		private int[][] doublet;


Line 61:		Line 61:
	public void makeDoubletMatrix() {		public void makeDoubletMatrix() {
	int n = wordList.size();		int n = wordList.size();
	doublet = new int[n + 1][n + 1];		doublet = new int[n + 1][n + 1];

	for(int from = 1; from <= n; from++) {		for(int from = 1; from <= n; from++) {
Line 68:		Line 68:
	String destination = wordList.get(to - 1);		String destination = wordList.get(to - 1);
	if (isDoublet(source, destination)) {		if (isDoublet(source, destination)) {
	doublet[from][to] = 1;		doublet[from][to] = 1;
	doublet[to][from] = 1;		doublet[to][from] = 1;
	}		}
	}		}
Line 99:		Line 99:
	continue;		continue;
	}		}
	if (doublet[from][to] == 1) {		if (doublet[from][to] == 1) {
	dfs(to);		dfs(to);
	}		}
Line 123:		Line 123:
	return start;		return start;
	}		}
	public static void main(String[] args) {		public static void main(String[] args) {
	DoubletsSimulator simulator = new DoubletsSimulator();		DoubletsSimulator simulator = new DoubletsSimulator();

Line 140:		Line 140:
	break;		break;
	}		}
	simulator.setEndToEnd(words.split(" ")[0], words.split(" ")[1]);		simulator.setEndToEnd(words.split(" ")[0], words.split(" ")[1]);
	simulator.dfs(simulator.getStartingPoint());		simulator.dfs(simulator.getStartingPoint());
	simulator.printResult();		simulator.printResult();

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:09Z

New page

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

== 소스 코드 ==
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]]

Doublets/황재선 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

imported>Unknown at 05:23, 7 February 2021