단어 제한 끝말 잇기
- 문제(알고스팟): https://algospot.com/judge/problem/read/WORDCHAIN
- 제한시간: 1초
문제에서 주의할 점
- 중복 단어 없음
- 모든 단어는 소문자
- 단어수 N(1 <= N <= 100)
- 100개의 단어를 진짜 다 이이어 보다가, 실패하면, 시작 단어나 중간에 이은 단어를 변경하는 형태로 만들면 시간 초과
- 힌트에서 마저 설명
문제에서 주어진 힌트
- 전체 주어진 단어에서, 어떤 단어로 시작해서, 어떤 단어로 끝나는지 주어지지 않음. 단어 끝말을 잇는 여러가지 경우의 수 중에 하나라도 끝말 잇기가 되면 답이 되는 문제임.
- 최악의 경우 100개 단어가 주어지고, 첫번째 단어를 첫번째 시작점으로 생각한 상태에서 99개까지 연결한다음, 100번째가 실패했을때, 99번째 연결을 바꾸어서 해보고, 100번째의 설공 실패를 가려서 실패하면, 98번째로 돌아와서 3개의 순서를 또 변경해보면서 연결 시도를 하는 형태로 구현하면, 답은 나오지만, 시간 초과에 걸린다.
- 100 * F(100-1) 형태임, 즉 ==> F(n) = n * F(n-1), (100 * 99 * 98 * 97 * ....) 최악의 경우...
- 즉 단어가 12개만 되어도, 4억7천번의 경우의 수가 생김 (5초 이상...)
- 문제 자체가 힌트임
- 단어의 시작 과 끝은 결국 a ~ z 에서 끝나게 됨
- 따라서 a ~ z 총 26개의 노드를 만들수 있음.
- 단어의 끝과 단어의 시작이 연결 될 수 있음, (e.g, god, dragon)는 g->d->n
- 따라서, 노드를 연결해보면, 방향이 있는 그래프가 된다.
- 문제에서 모든 단어를 연결하여 그 경우를 출력하라고 되어 있다.
- 방법이 여러개인 경우 아무거나 출력해도 된다고 되어 있음.
- 주의
- 자기가 자기로 돌아오는 경우 처리 (e.g, aa, bb)
따라서, 방향이 있는 그래프에서, 오일러 트레일을 만족하는 경우를 찾아서 출력하면 된다.
- 출력할때, 단어를 순서대로 출력하라고 되어 있음으로,
오일러 트레일사용시 방문 간선을 출력하는 형태로 생각 가능. - 이 문제를 오일러 트레일 문제로 인식하는게 중요.
풀이코드
Java로 풀이함
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;
class WordChainNode {
public String name;
public LinkedList<String> in;
public LinkedList<String> out;
public LinkedList<String> self;
public WordChainNode(String name) {
super();
this.name = name;
this.in = new LinkedList<String>();
this.out = new LinkedList<String>();
this.self = new LinkedList<String>();
}
public int getDegree() {
return in.size() + out.size();
}
public int inDegreeGap() {
return in.size() - out.size();
}
public int outDegreeGap() {
return out.size() - in.size();
}
@Override
public String toString() {
return "WordChainNode [name=" + name + "]" + "<in=" + in + ", out=" + out + "self=" + self + ">";
}
}
public class Main {
public static String IMPOSSIBLE = "IMPOSSIBLE";
public static LinkedList<String> path;
public static HashMap<String, WordChainNode> graph;
public static WordChainNode startNode, endNode;
public static int inputWordCnt;
public static void printPath(BufferedWriter bw) throws Exception {
for (int i = 0; i < path.size(); i++) {
bw.write(path.get(i) + " ");
}
bw.newLine();
}
// 방향있는 오일러 트레일
// 차수 홀수 노드가 0 or 2인 경우만 가능
// 차수 홀수 노드가 0이면, 아무 노드나 출발점이 되어도 됨
// 차수 홀수 노드가 2이면, 출발은 나가는 선이 하나 더 많고, 도착은 들어오는 선이 하나 더 많아야 함.
// 차수 짝수 노드는, 나가는선, 들어오는 선의 수가 동일해야 함.
public static String getStart() {
Set<String> keys = graph.keySet();
Iterator<String> it = keys.iterator();
LinkedList<WordChainNode> hol = new LinkedList<WordChainNode>();
String key = null;
for (; it.hasNext();) {
key = it.next();
WordChainNode node = graph.get(key);
if (node.getDegree() % 2 == 1) {
if (Math.abs(node.inDegreeGap()) > 1) {
return IMPOSSIBLE;
}
hol.add(node);
} else {
if (Math.abs(node.inDegreeGap()) > 0) {
return IMPOSSIBLE;
}
}
}
if (hol.size() == 0) {
// can any node
startNode = graph.get(key);
return key;
}
if (hol.size() == 2) {
WordChainNode a = hol.get(0);
WordChainNode b = hol.get(1);
if (a.outDegreeGap() == 1 && b.inDegreeGap() == 1) {
startNode = a;
endNode = b;
return a.name;
} else if (b.outDegreeGap() == 1 && a.inDegreeGap() == 1) {
startNode = b;
endNode = a;
return b.name;
}
}
return IMPOSSIBLE;
}
public static WordChainNode getConnectNode(String word) {
String connectNodeKey = word.charAt(word.length() - 1) + "";
WordChainNode connectNode = graph.get(connectNodeKey);
return connectNode;
}
// 오일러 트레일로 방문하고, 이를 저장
public static void visit(WordChainNode node) {
String word = "";
while (node.out.peek() != null) {
word = node.out.poll();
WordChainNode n = getConnectNode(word);
n.in.remove(word);
visit(n);
// 저장은 연결방문 이후에 하는게 핵심
path.addFirst(word);
}
// save node, 자기가 자기한테 다시 돌아오는 부분 단어 저장
while (node.self.peek() != null) {
path.addFirst(node.self.poll());
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = Integer.parseInt(br.readLine());
for (; tc > 0; tc--) {
inputWordCnt = Integer.parseInt(br.readLine());
// create graph
graph = new HashMap<String, WordChainNode>();
for (int wc = 0; wc < inputWordCnt; wc++) {
String word = br.readLine();
String first = word.charAt(0) + "";
String end = word.charAt(word.length() - 1) + "";
WordChainNode fNode = graph.get(first);
if (fNode == null) {
fNode = new WordChainNode(first);
graph.put(first, fNode);
}
WordChainNode eNode = graph.get(end);
if (eNode == null) {
eNode = new WordChainNode(end);
graph.put(end, eNode);
}
if (first.equals(end)) {
fNode.self.add(word);
} else {
fNode.out.add(word);
eNode.in.add(word);
}
}
// check possible
String startNodeName = getStart();
if (startNodeName == IMPOSSIBLE) {
bw.write(IMPOSSIBLE + "\n");
} else {
path = new LinkedList<String>();
visit(startNode);
printPath(bw);
}
}
br.close();
bw.flush();
bw.close();
}
}