헤밀토니안 경로2 WORDCHAIN - 단어제한 끝말잇기 (오일러 경로, 헤밀토니안 경로) https://algospot.com/judge/problem/read/WORDCHAIN 헤밀턴 경로 문제를 오일러경로 문제로 바꾸는 것이 포인트. 모든 정점을 지나는 경로->모든 간선을 지나는 경로 https://suuntree.tistory.com/176코드자세한설명 단어들이 최대 100개 주어질 때, 이 단어들을 단 한번씩만 이용해서 모든 단어들을 사용할 수 있는지 출력. 사용할 수 있다면 그 순서중 아무거나 출력. 모든 단어들을 사용할수 있는지에 대해 그래프를 형성하면, 헤밀토니안 경로를 찾는 문제가 된다.(모든 정점을 정확히 한 번씩 지나는 경로. 외판원 순회(TSP)는 이 경로 중 가장 작은 가중치를 갖는 경로.) 헤밀턴 경로를 찾는 유일한 방법은 조합탐색으로 이 문제의 경우 단어 개수 n!만.. 2020. 2. 12. 오일러 경로 '한붓그리기' 로 모든 간선을 칠한다면 그게 바로 오일러 경로 오일러 경로가 존재하려면 1. 출발점=도착점인 경우 (오일러 서킷) 양방향: 모든 정점의 차수가 짝수면 된다. 단방향: 모든 정점의 indegree==outdegree 2. 출발점 != 도착점인 경우 (오일러 트레일) 양방향: 출발점과 도착점의 차수는 홀수고 나머지 정점의 차수는 짝수면 된다. 단방향: outdegree[i]==indegree[i]+1인 점(시작점) 단 한개, indegree[i]==outdegree[i]+1인 점(도착점) 단 한개 존재. 컴포넌트가 여러 개인 경우 당연히 오일러 서킷이 존재하지 않을 거라고 생각할 수 있지만, 컴포넌트의 정점이 하나인 경우 간선이 존재하지 않는다는 점을 유념해야 한다. -> 모든 간선이 하나의.. 2020. 2. 12. 이전 1 다음