[백준] No.18250 - 철도 여행 (C++, 오일러 경로)

문제

 

www.acmicpc.net/problem/18250

18250번: 철도 여행

 

풀이

 

solved.ac 난이도: Platium 4

 

 

오일러 서킷(Eulerian curcit)과 오일러 경로(Eulerian trail)를 알아야 해결 가능한 문제.

분류를 알고 풀어서 풀만 했지만 분류를 모르면 정말 풀기 힘들었을 듯한 문제였다.

 

일단 오일러 서킷과 경로를 집고 넘어가자.

 

오일러 서킷(Eulerian curcit)

오일러 서킷은 모든 그래프의 간선을 한 번씩만 순회하여 시작점으로 돌아오는 경로를 의미한다.

이를 만족시키는 조건은 모든 노드가 짝수의 간선(edge)를 갖는 경우인데,

이는 시작점에서 탈출한 후에 다시 시작점으로 돌아올 간선이 쌍을 이루어야 하기 때문이다.

다른 노드들도 마찬가지로 진입했다면 다음 노드로 탈출할 간선이 쌍을 이뤄야 시작점으로 돌아갈 수 있다.

따라서 노드의 인접 간선의 개수를 차수(degree)라고 하면 

오일러 서킷을 만족시키는 조건은 모든 노드의 차수가 짝수인 경우이다.

 

이번 문제에서 예를 든다면 아래와 같이 그래프가 사이클을 이루는 경우이다.

모든 노드의 차수는 2이기 때문에 어디든 시작점이 되어 모든 간선을 순회하고 시작점으로 되돌아올 수 있다.

이런 경우 철도 여행은 한번에 가능하다.

 

오일러 경로/트레일(Eulerian trail)

오일러 경로(트레일)은 모든 간선을 순회하지만 시작점과 끝점이 다른 경우이다.

이를 만족시키는 조건은 시작점과 끝점만 홀수 차수를 가지고 나머지 노드는 짝수 차수를 가지는 경우이다.

시작점은 시작시 다른 노드로 이동하는 간선 1개와 짝수의 간선을

끝점은 경로의 마지막으로 진입하는 간선 1개와 짝수의 간선을 가지므로 홀수의 차수가 된다.

나머지 노드들은 진입했다면 탈출해야 하기 때문에 짝수의 간선을 가진다.

 

이번 문제에서는 발생할 수 있는 오일러 경로의 개수를 세는 것이 가장 중요하다.

 이는 홀수 차수의 노드 수로 철도 여행의 횟수를 계산할 수 있기 때문이다.

 

문제의 예제를 통해 이를 확인해보자.

위와 같은 철도를 그래프로 축약해서 나타내면 다음과 같다.

해당 그래프에서 홀수 차수를 가지는 노드는 차수 1의 1, 5, 7번 노드와 차수 3의 3번 노드이다.

 

철도 여행을 하는 경로, 즉 오일러 경로는 홀수 차수의 노드에서 시작하여 홀수 차수의 노드에서 끝난다.

따라서 위의 4개의 홀수 차수 노드를 한 쌍씩 짝지으면 철도 여행의 경로가 생성된다.

 

예를 들어 1-3, 5-7 끼리를 짝지으면 아래와 같은 경로가 생긴다.

1-5, 3-7 을 짝짓든 1-7, 5-3을 짝짓든 결국 두 개의 쌍이 생성되어 두 개의 경로를 만드는 것을 변하지 않는다.

다른 형태의 그래프에서도 홀수 차수의 노드가 짝을 지어 경로를 생성하는 것은 동일하다.

 

위와 같은 그래프에서는 홀수 차수의 노드가 6개이므로 3개의 경로가 생성 가능하다.

 

 

정리하면, 그래프의 모든 노드의 차수가 짝수라면 해당 그래프는 한 번에 모든 간선(철도)를 순회할 수 있으므로 철도 여행은 한 번에 가능하다.

그래프의 노드 중에 홀수 차수의 노드가 있다면 (홀수 차수의 노드 수)/2가 생성할 수 있는 오일러 경로의 수이자, 철도 여행의 횟수가 된다.

 

단, 도시들이 모두 철도로 서로 이어지지 않을 수 있기 때문에(같은 그래프에 속하지 않을 수 있음.) 

DFS 형식으로 방문하지 않은 노드들만 방문하며 해당 그래프의 홀수 차수의 개수를 세어주고, 모든 그래프에서의 경로 수를 결과로 더해주자.

또한, 도시 중에 어떠한 도시로도 철로로 이어지지 않은 도시도 있을 수 있기 때문에 예외처리에 주의하자.

 

 

코드