알고리즘 템플릿

• 코드

정의

그래프 상에 존재하는 모든 간선을 1번씩만 지나는 경로. 아래는 오일러 경로의 예시이다.

위의 그림처럼 간선으로 연결돼 있지 않은 다른 컴포넌트에서 간선이 존재하지 않는다면 이 또한 오일러 경로가 된다는 점에 주의하자. 따라서 아래와 같이 다른 컴포넌트에도 간선이 존재할 경우의 예시는 오일러 경로가 아니다.

주로 ‘이러한 경로가 존재하는가?’ 하는 문제가 나오는 것 같다.

파악하는 방법은 아래와 같다.

1. 각 노드로부터 연결된 ‘간선의 개수가 홀수’인 노드의 개수가 2개보다 많다면 오일러 경로가 될 수 없다.
2. 서로 다른 컴포넌트가 존재하는지 확인한다.
   1. 서로 다른 컴포넌트 중 2개 이상의 컴포넌트에 간선이 존재한다면 오일러 경로가 될 수 없다.
   2. 1개 이하의 컴포넌트에서만 간선이 존재한다면 오일러 경로가 된다.

문제 및 풀이 코드

16188 - 퍼레이드

오일러 경로가 존재하는지 파악하는 문제.

모든 점은 최소 1개 이상 간선으로 연결됨이 보장되기 때문에, 분리된 컴포넌트가 존재한다면 반드시 오일러 경로가 될 수 없어 검증 부분을 간단히 구현할 수 있다.

• 코드

1696 - 색 막대 (https://www.acmicpc.net/problem/1696)