그래프 오일러 서킷 문제1 - 단어 제한 끝말 잇기

문제 파악

내가 생각한 접근법은 단어를 vertex로 보는 것이었다. 그러나 이렇게 그래프를 만든 뒤 오일러 서킷을 찾는 알고리즘을 실행시키면, 같은 단어를 두 번 사용하는 경우까지 따지게 되어 문제의 조건을 만족하지 못한다는 문제점이 생긴다.
그래서 해밀턴 경로를 찾는 알고리즘을 생각해 보았지만 해밀턴 경로를 찾는 알고리즘은 시간복잡도가 매우 큰 알고리즘이라 포기했다.

올바른 풀이

• vetex와 edge 설정
  올바른 풀이법은 한 단어가 중복으로 사용되는 것을 막기 위해 단어가 아니라 알파벳을 vertex로 보는 것이다. 시작이나 끝에 오는 알파벳은 여러 번 사용되도 문제 없기 때문에 이렇게 보는 것이 올바르다. 오일러 서킷을 찾는다는 것 자체가 엣지를 정확히 한 번씩만 사용하는 경로를 찾는 것이기 때문에, 문제의 조건인 단어를 정확히 한 번씩만 본다는 조건에 부합하려면 알파벳을 vertex로, 단어를 edge로 보는 방향이 맞는 것이다.
• 그래프 만들기
  그래프를 만들기 위해 입력 받은 단어를 하나씩 확인하면서 처음 오는 문자와 끝에 오는 문자를 확인한다. 오일러 서킷과 트레일러를 찾을 때 확인하기 위해 이차원 벡터 adj와 일차원 벡터 outdegree, indegree를 선언한다.
  adj[i][j]의 값은 i로 시작해서 j로 끝나는 단어의 수이다.
  indegree[i]는 i로 시작하는 단어의 수이다.
  outdegree[j]는 j로 끝나는 단어의 수이다.
  여기서 주의할 점은 만약에 dog라는 단어가 들어오게 되면 d에 대한 indegree가 1증가하고 g에 대한 outdegree가 1증가하는 것이 아니라, d에 대한 outdegree가 1 증가하고 g에 대한 indegree가 1 증가한다는 것이다.
  이는 어차피 오일러 서킷 또는 트레일이 존재하는 경우를 가정하고 있기 때문이다. 만약에 위의 가정이 틀리게 된다면 오일러 서킷이나 트레일이 존재하지 않기 때문에 이를 판별하기 위해 사용하는 변수이다.
• 오일러 서킷, 트레일 찾기
  이제 만들어진 그래프를 바탕으로 오일러 서킷 또는 그래프를 찾아야 한다. 오일러 서킷을 찾는 알고리즘은 전 글의 알고리즘과 같지만, 이 문제의 그래프는 유향 그래프이기 때문에 한 번 경로를 이동할 때 마다 간선을 하나 씩만 지워줘야 한다.
  먼저 트레일인 경우와 서킷인 경우의 조건이 다르다. 트레일인 경우 경로가 사이클을 이루지 않기 때문에 반드시 시작 지점과 끝 지점이 존재하고 시작 지점에 있는 알파벳은 그 알파벳으로 끝나는 단어의 숫자보다 그 알파벳로 시작하는 단어의 숫자가 한 개 더 많다.
  예시를 들어 설명하자면, dog가 트레일의 시작 지점이 되려면 d로 시작하는 단어의 숫자는 d로 끝나는 단어의 숫자보다 한 개 적다. 만약 d로 끝나는 단어의 숫자와 시작하는 단어의 숫자가 같게 된다면 그 단어를 통해 dog로 다시 돌아올 수 있기 때문이다.
  이 논리를 통해 트레일을 찾는다. 트레일이 아닐 경우 반드시 서킷이 존재하기 때문에 이 후로는 서킷을 찾는 알고리즘을 동작시킨다. 서킷의 경우 어느 vertex에서 시작해도 결과는 항상 같다.
• 서킷, 트레일의 존재 여부 확인
  위 과정은 서킷이나 트레일이 반드시 존재한다고 가정하고 전개한 알고리즘이다. 그렇기 때문에 위에 앞서 반드시 서킷이나 트레일이 존재하는지 확인하는 과정을 거쳐야 한다.
  이 과정 역시 outdegree와 indegree의 원소를 활용한다.
  outdegree[i]에서 indegree[i]를 뺀 값을 delta라고 두자.

만약 delta가 -1,0,1이 아닌 다른 값이 나오게 되면 한 알파벳으로 시작하는 단어와 끝나는 단어 수의 차이가 2 이상이라는 얘기가 되므로 절대 끝말 잇기를 완성할 수 없으므로 false를 리턴한다

delta의 값이 1이면 plus라는 변수를 1증가 시켜주고 -1이면 minus라는 변수를 1 증가시켜준다. 한 알파벳으로 끝나는 단어와 시작하는 단어의 수가 1차이 난다는 것은 그 알파벳이 트레일의 시작 정점 또는 끝 정점이라는 뜻이다. 따라서 delta가 1이 되는 경우는 반드시 plus 1번, minus 1번으로 쌍을 이루어야 한다. 1번을 넘어서거나 쌍을 이루지 않는 경우에는 트레일이 존재하지 않기 때문에 false를 리턴한다.

최종 문제 해결 과정

• 주어진 단어를 통해 알파벳을 정점으로 하는 그래프를 생성한다. 그래프를 생성하는 과정에서 특정 알파벳으로 시작하는 단어와 끝나는 단어의 수 를 기록한다.

• 오일러 서킷 또는 트레일이 존재 하는지 확인한다.

• 오일러 서킷 또는 트레일이 존재하지 않는 경우 IMPOSSIBLE을 리턴한다

• 오일러 서킷 또는 트레일이 존재한다면 오일러 서킷 알고리즘을 통해 찾는다.