오일러 서킷

단어 제한 끝말잇기 (WORDCHAIN)

algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 www.algospot.com DFS, 오일러 서킷, 오일러 트레일 1. 문제 해결 아이디어 끝말잇기에 사용되는 단어들이 주어진다. 주어진 단어 모두를 사용해서 끝말잇기를 만들면 된다. -> 오일러 회로임을 알 수 있다. 단어를 모두 사용해서 다시 시작점으로 돌아올 수도 있고, 시작점이 아닌 지점에서 끝날 수도 있다. 다시 시작점으로 돌아오는 경우는 오일러 서킷이라고 할 수 있다. 모든 간선을 한 번씩 통과하지만 시작점이 아닌 다른 정점에서 끝나는 경로를 오일러 트레일 이라..

오일러 서킷

오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로 -> 한붓그리기 그래프의 시작점을 u, 끝점을 v라고 하자 1. u != v 인 경우 : v는 항상 홀수 개의 간선과 인접한다. v를 지나기 위해서 v로 들어가는데 하나, 나가는데 하나가 필요하다. 만약 v가 끝점이라면 v로 들어가는 간선에 대응하는 나가는 간선이 없다는 뜻이므로 v에 인접한 간선의 수가 홀수 일 수밖에 없다. 2. u == v 인 경우 : v는 항상 짝수 개의 간선과 인접한다. u에서 나가는 것으로 시작했기 때문에 u로 다시 들어왔다면 u(=v)에 인접하는 간선의 수는 짝수이다. 한 정점에 인접한 간선의 개수를 degree라고 하자. 오일러 서킷은 모든 정점에 들어가는 횟수와 나가는 횟수가 같아야하므로..