[알고스팟] WORDCHAIN - 단어 제한 끝말잇기 (C++, 오일러 경로)

문제

 

https://algospot.com/judge/problem/read/WORDCHAIN

algospot.com :: WORDCHAIN

 

 

풀이

 

종만북 난이도: 하

 

DFS로 오일러 서킷(Eulerian curcit)과 오일러 경로(Eulerian trail)을 구현하는 문제.

 

오일러 서킷(Eulerian curcit)

오일러 서킷은 모든 그래프의 간선을 한 번씩만 순회하여 시작 노드로 돌아오는 경로를 의미한다.

오일러 서킷을 만족시키는 그래프는 모든 노드가 짝수의 간선(edge)를 갖는 경우이다.

 

모든 노드가 짝수의 간선을 가진다면 특정 노드로 진입한 경우 다른 노드로 가는 간선이 항상 남아있다.

즉, 진입과 탈출이 항상 쌍을 이루어야 하기 때문에 짝수의 간선이 필요하다.

시작점에서 출발을 했다면 시작점으로의 집입 간선은 항상 남아있기 때문에 시작 노드로 돌아올 수 있다.

만약 방향 그래프라면 모든 노드의 진입 간선 수(indegree)  = 탈출 간선 수(outdegree)가 같아야 한다.

 

오일러 경로/트레일(Eulerian trail)

오일러 트레일은 모든 간선을 한 번씩만 순회하되 시작점과 끝점이 다른 경로를 의미한다.

이 경우에는 시작점과 끝점은 홀수의 간선, 나머지 노드들은 짝수의 간선을 가져야 한다.

시작점은 되돌아 최종적으로 오지 않아야 하므로 시작 간선(1개) + 짝수의 간선(2n개)을,

끝점은 최종적으로 진입하여 종료되어야 하므로 짝수의 간선(2k 개) + 최종 종료 간선(1개)으로 각각 홀수의 간선을 가진다.

만약 그래프가  방향이 있다면

시작점은 진입 간선 수(indegree) + 1 = 탈출 간선 수(outdegree) 

끝점은 진입 간선 수(indegree) = 탈출 간선 수(outdegree) +1 이다.

 

 

문제로 돌아와서 생각해보자.

끝말잇기에서 중요한 것은 각 단어의 시작 알파벳과 끝 알파벳이다.

dog와 같은 단어는 d에서 시작에 g로 끝난다. 

따라서 다음 단서는 g로 시작해야 할 것이다.

이를 그래프로 나타내 보면 d노드에서 g노드로 이동하는 방향 그래프로 나타낼 수 있다.

 

끝말잇기 단어 목록을 모두 사용하기 위해서는 결국 각 단어를 위와 같이 표현한 그래프에서 모든 간선을 순회해야 한다.

따라서 그래프의 간선을 순회하는 두 가지 경로 오일러 서킷 또는 트레일을 만족해야 한다.

만약 두 경로에 해당하지 않는다면 모든 간선을 순회하지 못하는 경우임으로 impossible을 출력해주자.

 

 

예제의 dog, god, dragon, need를 그래프로 표현하면 다음과 같다.

위의 그래프에서는 모든 노드가 진입 간선 수(indegree)  = 탈출 간선 수(outdegree) 로 짝수의 간선 수를 갖는다.

따라서 오일러 서킷 경로를 만족시킨다.

 

그리고 aa, ab, bb의 경우

 

a는 오일러 트레일의 시작점, b는 오일러 트레일의 끝점의 조건을 만족하므로 오일러 트레일에 해당한다.

 

 

이를 구현하기 위해

adj[start_alphabet][end_alphabet]에는 start_alphabet에서 시작하여 end_alphabet로 끝나는 단어의 개수를

out_degree[start_alphabet]에는 start_alphabet에서 탈출하는 간선의 수

in_degree[end_alphabet]에는 end_alphabet로 진입하는 간선의 수를 저장하였다.

 

이제 다음과 같은 for문을 돌면서 각 알파벳의 진입 차수(indegree)와 탈출 차수(outdegree)를 확인하자.

 

    bool is_possible = true;
    int pos_start_cnt=0, pos_end_cnt=0;
    for(int i=0; i<26 ; ++i){
      if(abs(out_degree[i]-in_degree[i]) == 1){
        if(out_degree[i]-in_degree[i] == 1){  //start node가 가능한 경우
          start_alphabet = i;
          if(++pos_start_cnt >1){
            is_possible = false;
            break;
          }
        }else{
          if(++pos_end_cnt >1){
            is_possible = false;
            break;
          }
        }
      }else if(abs(out_degree[i]-in_degree[i]) > 1){  //불가능한 그래프
        is_possible = false;
        break;
      }
    }
 
    if( (pos_start_cnt == 1 && pos_end_cnt== 0) || (pos_start_cnt == 0 && pos_end_cnt== 1))
      is_possible = false;

 

 

만약에 out_degree[i] - in_degree[i] == 1 인 알파벳이 있다면

해당 알파벳은 오일러 트레일의 시작점이 될 수 있다.

하지만 시작점이 가능한 조건의 알파벳이 두 개  이상이라면 해당 그래프는 오일러 트레일을 만족시키지 못한다.

 

또한 시작점이 있다면 끝점도 한 개씩 존재해야 오일러 트레일이 가능하다.

따라서 끝점이 가능한 알파벳의 개수도 세어 조건을 확인하자.

 

만약 abs(out_degree[i]-in_degree[i]) > 1인 경우 오일러 트레일은 물로 오일러 서킷도 불가능하다.

 

시작점이나 끝점이 모두 한 개씩 있거나 모든 알파벳의 진입 차수(indegree)와 탈출 차수(outdegree)가 같다면

시작점에서부터 DFS로 각 점을 순회하여 종료 시점을 기록하면 경로를 구할 수 있다.

 

void WordChainDFS(queue<int>& que ,int idx){
  for(int i=0; i<26 ; ++i){
    if(adj[idx][i] !=0){
      --adj[idx][i];
      WordChainDFS(que,i);
    }
  }
  que.push(idx);
}

 

 

 

코드