[백준] 1199 오일러 회로

문제소개

---

1199 오일러 회로 문제는 오일러 경로 문제입니다. ㅎ,ㅎ;

오일러 경로란 그래프에 존재하는 모든 간선을 한번씩만 사용하여 연결하는 경로이며 그래프에서 오일러 경로가 존재하기 위해서는 그래프 내의 모든 노드는 2배수의 차수를 가져야합니다. 여기서 차수란 노드에 인접한 간선을 의미합니다. 이러한 조건을 이용해서 그래프 내에서 오일러 경로의 존재 유무를 파악할 수 있습니다. 자세한 설명은 링크를 참조해주세요.

 

 

문제풀이

---

오일러 경로는 Hierholzer's algorithm을 이용하여 해결할 수 있으며 알고리즘 순서는 다음과 같습니다.

 

0. 해당 그래프에 오일러 경로가 존재

1. 적당한 시작 노드를 선택합니다.

2. 노드에 연결되어 있는 간선들 중 사용하지 않은 간선을 따라 다음 노드로 이동합니다.

3. 해당 노드의 방문 여부를 판별하고 방문한 노드면 오일러 싸이클을 이므로 종료를 합니다.

   그렇지 않으면 2,3번을 반복합니다.

 

BEGIN

IF graph infeasible THEN END

start ← suitable node

tour ← {start}

REPEAT

current = start ← node in tour with
unvisited edge

subtour ← {start}

DO

{current, u} ← take unvisited edge

subtour ← subtour ∪ {u}

current ← u

WHILE start ≠ current

Integrate subtour in tour

UNTIL tour is Eulerian cycle/path

END

 

다음과 같이 6개의 노드로 이루어진 그래프가 있습니다. 모든 노드는 2의 배수로 in - out 의 간선을 가지고 있습니다. 

 

오일러 경로를 찾기 위해서 먼저 1번을 시작 노드로 선택하였습니다.

DFS를 이용하면 1 > 2 > 4 > 3 > 1 순서로 노드를 탐색합니다.

더 이상 이동할 수 있는 간선이 없을 때 해당 노드의 번호를 출력합니다.

그러면 1 > 3 > 4 의 순서로 노드 번호를 출력하다가 4번 노드에서 이동할 수 있는 간선이 존재 하므로 5 > 6 > 4 로 이동합니다. 동일하게 더 이상 이동할 수 있는 간선이 없을 때 해당 노드의 번호를 출력합니다.

정리하면 1 > 3 > 4 > 6 > 5 > 4 > 2 > 1 번의 순서로 오일러 회로를 그릴 수 있습니다.

 

 

---

소스보기