1199. 오일러 회로

1199번: 오일러 회로

---

오일러 회로란, 하나의 정점에서 출발하여 모든 간선을 한 번씩만 거쳐서 출발점으로 돌아오는 경로를 말한다. 출발점과 도착점이 같기 때문에 회로(Circuit)이라는 이름이 붙었다. 출발점과 도착점이 다르면 오일러 경로라고 한다.

 

문제를 풀기 위해 일단 이런 생각을 해 보았다.

 

• 그래프의 정점이 2개일 때, 두 정점을 연결하는 간선의 수가 짝수여야만 오일러 회로가 존재한다.
• 정점이 3개일 때도 마찬가지로 연결된 모든 두 정점은 짝수개의 간선으로 연결되어야 한다.
• 그렇다면 모든 정점 사이의 간선 개수가 짝수여야만 하는 것이 아닐까?

고수분께 질문해 본 결과 오일러 회로를 구하는 알고리즘이 따로 있다고 하여 공부해 보았다.

[그래프] 오일러 회로

알고리즘이 매우 직관적이다. 단 두 문장으로 설명되며 코드를 작성할 수도 있었다.

---