[그래프] [시도x] WORDCHAIN 단어 제한 끝말잇기

1. 문제

 

끝말잇기

 

참가자 = 원으로 앉아있음

 

시계방향으로 단어를 말함

 

단어의 첫글자 = 이전사람이 말한 글자의 끝

 

단어의 종류가 정해짐

 

한단어 두번X

 

단어들을 전부 사용가능한지 판단하고

 

어떤 순서로 단어를 사용해야하는지를 계산하는 문제

 

 

2. 오일러 트레일

 

이 문제는 각 단어의 첫부분과 끝부분으로 만들어진 간선을 가지는 그래프를 만들고

 

오일러 트레일과 오일러 경로 구하는 문제인것 같다.

 

하지만 책에서 구현한 오일러 경로를 아직 이해하지 못하겠다.

 

간선이 아닌 정점을 벡터에 집어넣는것, 아직 생각을 더해야 겠다.

 

 

또한 그래프를 생성하고 홀수점이 2개일때 오일러 트레일을 찾을려면

 

홀수점 두개중에서 시작점과 끝점을 찾아야하는게 문제이다.

(책의 풀이를 보고, 방향그래프인점을 생각하지 못한 것을 알게되었다.)

 

 

3. 책의 풀이: 그래프 생성

 

일단 그래프를 만들어야한다. 이 그래프의 정점들은 알파벳의 각 글자를 표현하며.

 

각 단어는 첫글자에서 마지막 글자로 가는 간선이 된다.

 

그래프를 만든 후 오일러 트레일과 오일러 서킷을 찾으면 답이된다.

 

책에서는 시작하는 단어의 수와 끝나는 단어의 수를 기록하여경로의 시작점을 쉽게 찾아냈다.

vector<vector<int> > adj;
 
vector<string> graph[26][26];
 
vector<int> indegree, outdegree;
 
void makeGraph(const vector<string>& words) 
{
    for(int i = 0; i < 26; i++)
    {
        for(int j = 0; j < 26; j++)
            graph[i][j].clear();
    }
 
    adj = vector<vector<int> >(26, vector<int>(26, 0));
    indegree = outdegree = vector<int>(26, 0);
 
    for(int i = 0; i < words.size(); i++)
    {
        int a = words[i][0] - 'a';
        int b = words[i][words[i].size() -  1] - 'a';
        graph[a][b].push_back(words[i]);
        adj[a][b]++;
        outdegree[a]++;
        indegree[b]++;
    }
}

 

 

4. 책의 풀이: 방향 그래프에서의 오일러 서킷과 오일러 트레일 

 

방향 그래프에서의 오일러 서킷은 무향 그래프와 다르지 않지만

 

오일러 서킷의 존재 조건이 무향 그래프와 다르다.

 

오일러 서킷의 모든 점에서는 경로가 들어온 횟수와 나간 횟수가 같아야하기 때문이다.

 

방향 그래프에서는 각 간선은 둘중 한 방향으로만 쓸 수 있다.

 

 

오일러 트레일 (a->,,->b) 는

 

간선 (b->a)를 추가해서 오일러 서킷을 찾을 수 있다는 점에서  

 

오일러 트레일의 조건을 찾을 수 있다.

 

a에서 나가는 간선이 들어오는 간선보다 하나 많고,

 

b에서는 들어오는 간선이 나가는 간선보다 하나 많고,

 

다른 모든 정점에서는 두개의 간선이 같아야한다.

 

 

 

 

 

5. 책의 풀이: 오일러 서킷 혹은 트레일 탐색 구현

 

우리가 찾는 경로는 오일러 서킷일 수도 있고, 트레일일 수도 있다.

 

이는 각 정점의 차수를 확인하여 서킷인지 트레일인지, 아니면 성립하지 못하는지 판단 하면 된다.

 

void getEulerCircuit(int here, vector<int>& circuit) 
{
    for(int there = 0; there < adj.size(); there++)
    {
        while(adj[here][there]>0)
        {
            adj[here][there]--;
            getEulerCircuit(there, circuit);
        }
    }
    circuit.push_back(here);
}
 
vector<int> getEulerTrailOrcircuit() 
{
    vector<int> circuit;
 
    for(int i = 0; i < 26; i++)
    {
        if(outdegree[i] == indegree[i] + 1) {
            getEulerCircuit(i, circuit);
            return circuit;
        }
    }
 
    for(int i = 0 ; i < 26; i++) 
        if(outdegree[i]) {
            getEulerCircuit(i, circuit);
            return circuit;
        }
    return circuit;
}

 

 

6. 책의 풀이: 오일러 서킷과 트레일의 존재 여부 확인

 

 

생성한 그래프의 정점들의 차수를 검사하고

 

dfs를 통해 생성된 서킷이 모든 간선을 방문했는지 확인하면 된다.

 

시작점 + 간선의 개수 이므로 

 

총 circuit의 사이즈는 words.size()  + 1 이어야한다.

 

 

 
bool checkEuler()
{
    int plus1 = 0; minus1 = 0;
    for(int i = 0; i < 26; i++)
    {
        int delta = outdegree[i] - indegree[i];
 
        if(delta < -1 || 1 < delta) return false;
        if(delta == 1) plus1++;
        if(delta == -1) minus1++;
    }
    return (plus1 == 1 && minus1 == 1) || (pluus1 == 0 && minus1 == 0);
}
 
string solve(const vector<string>& words) 
{
    makeGraph(words);
    if(!checkEuler()) return "IMPOSSIBLE";
    vector<int> circuit = getEulerTrailOrcircuit();
    if(circuit.size() != words.size() + 1) return "IMPOSSIBLE";
 
    reverse(circuit.begin(), circuit.end());
    string ret;
    for(int i = 1; i < circuit.size(); i++)
    {
        int a = circuit[i-1], b = circuit[i];
        if(ret.size()) ret += " ";
        ret += graph[a][b].back();
        graph[a][b].pop_back();
    }
    return ret;
}

 

 

 

WORDCHAIN

algospot.com :: WORDCHAIN

 

 

- 알고리즘 문제해결전략 844p