[ 개념 ] 42. 오일러 경로, 오일러 회로

> 오일러 경로, 오일러 회로

이번에 소개할 내용은 오일러 경로(Eulerian trail) 및 오일러 회로(Eulerian circuit)입니다.

위상수학, 이산구조 시간의 그래프 이론 챕터에서 한 번쯤 보셨을 내용입니다.

무향이나 유향 그래프가 있을 때, 그래프에 존재하는 모든 간선을 정확히 1번씩만 방문하는 연속된 경로가 바로 이것들입니다.

이때 시작점과 도착점이 같으면 오일러 회로가 되고, 아닐 경우 그냥 오일러 경로가 됩니다.

이와 같은 무향 그래프가 있을 때, 경로 [A, B, C, D, A]는 시작점으로 돌아오기는 했으나 모든 간선을 사용하지는 않으므로 오일러 회로가 아니지만(물론, 오일러 경로조차 아닙니다),

경로 [A, B, C, E, F, C, D, A]는 오일러 회로입니다. 모든 간선을 정확히 한 번씩 거쳤기 때문이죠.

이걸 사용하는 응용문제는 정말 가뭄에 콩 나듯 드문 편이고, 그냥 어떻게 오일러 경로를 찾는가 정도만 알려드리려 합니다.

정말 가끔씩 응용문제가 대회에 출제될 때가 있는데, 하나같이 다 개막장 난이도를 자랑하기에 이 글에 함부로 싣지를 못하겠습니다.

먼저 오일러 경로의 존재여부를 판단하는 방법은 너무 유명해서 다들 아실 겁니다.

무향 그래프의 경우, 차수(degree)가 홀수인 정점이 2개일 때 오일러 경로(회로가 아닌)가, 0개일 때 오일러 회로가 존재하고

오일러 경로는 시작점과 끝점을 차수가 홀수인 정점 2개로 하며, 오일러 회로는 존재만 한다면 그 어떤 정점을 시작점으로 뽑아도 만드는 것이 가능합니다.

당장 위 그래프를 보면 각 정점의 차수가 다 짝수이고, 따라서 오일러 회로가 존재합니다.

이건 시작점과 끝점을 제외하고서는 들어오는 간선이 있다면 반드시 나가는 간선이 하나 더 마련되어 있어야 하기 때문이죠. 항상 차수가 2의 배수꼴로 붙게 됩니다.

유향 그래프에서 오일러 회로가 존재하려면 모든 정점에 대해 indegree와 outdegree가 일치해야 합니다. 위와 같은 맥락이죠.

회로가 아닌 오일러 경로라면 indegree가 1 적은 정점 하나가 시작점, outdegree가 1 적은 정점 하나가 끝점으로 정해지며 다른 indegree와 outdegree가 불일치하는 정점이 더 있으면 안 됩니다. 물론 1씩 차이가 나지 않아도 안됩니다.

또한 유향/무향 관계없이, 서로 다른 컴포넌트에 각각 간선이 존재해도 오일러 경로는 존재할 수 없습니다. 두 컴포넌트 자체가 떨어져 있어서 절대 경로를 이을 수 없기 때문.

그러나 간선만 없다면 떨어져 있는 정점이 있어도 오일러 경로는 존재합니다! 이게 무진장 큰 함정이었습니다...

그럼 이제 오일러 회로를 구해볼 것인데요. 위키에 실려 있는 현재 가장 널리 알려졌고 효율적인 알고리즘은 Hierholzer's Algorithm입니다.

이 알고리즘은 말로 풀어쓰면 정말 너무나도 간단한데,

1. 아무 정점 v를 뽑고 v에서 출발해 v로 돌아오는 경로를 하나 뽑는다.
2. 이때, 위 경로에 속해있는 정점 중 인접한 간선들 중에 경로에 쓰이지 않는, 즉 아직 방문되지 못한 간선이 있는 정점 u가 존재하면, u에서 시작해서 아직 쓰이지 않은 간선들만 사용해 u로 돌아오는 경로를 하나 더 찾아 원래의 경로에 끼워넣는다.

그러니까..

위 그래프에서 시작점을 A로 놓고 경로 [A, B, C, D, A]를 찾았다고 합니다.

그러나 이 중 정점 C는 아직 사용하지 않은 인접한 간선이 존재합니다.

따라서 C에서 또다른 경로 [C, E, F, C]를 찾아서 원래의 경로에서 C가 있던 자리에 대체해서 끼워 넣으면,

[A, B, C, E, F, C, D, A]가 되어 오일러 회로가 완성됩니다.

물론 여기서 항상 끝나지는 않고, 또 경로 [C, E, F, C]의 정점들 중에서 아직 사용하지 않은 인접간선이 남아있는 정점이 존재한다면 재귀적으로 또 경로를 구해 끼워넣어야 합니다.

말로 풀어쓰자니 진짜 지극히 간단한데, 도대체 이걸 어떻게 할 거냐는 게 문제.

해결방법은 "재귀적"이라는 표현에서 알 수 있듯이 DFS입니다.

방문을 하면서 해당 간선을 사용한 것으로 표시하거나 지우고 간선 양쪽의 차수를 1씩 줄여 나가는데,

해당 정점의 방문 함수가 끝나는 순간에 정점 번호를 출력하면 이걸 이어붙인 게 정답이 됩니다!

A->B->C 순으로 방문했다고 합시다. 만약 여기서 D를 먼저 택해도, D->A로 가서 A의 이웃이 더 없으므로 방문이 끝나 C로 돌아오면서 "A D"를 출력하게 됩니다.

그 다음 남은 정점 E를 선택해서 C->E->F->C로 가면 C도 더 이상 이웃이 없어서 그대로 돌아가며 "C F E C"를 출력하고,

C에서도 시작점인 A로 돌아가면서 "B A"를 출력하면...

이걸 다 이어붙이면 "A D C F E C B A"가 되고 이건 오일러 회로입니다.

만약 A->B->C를 방문하고 D가 아니라 E를 먼저 방문했다고 해도, C->E->F->C를 방문한 후 C에서 이제 유일하게 남은 D를 방문하는 순서를 거치게 되고

결과를 이으면 "A D C F E C B A"가 되어서 또 오일러 회로입니다.

-BOJ[1199] : 오일러 회로

https://www.acmicpc.net/problem/1199

[

1199번: 오일러 회로

첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러

www.acmicpc.net

](https://www.acmicpc.net/problem/1199)

오일러 회로를 찍어봅시다.

참고로 자기 자신으로 돌아오는 간선은 없습니다!

#include <cstdio>
#include <vector>
using namespace std;

// 간선 구조체
struct Edge{
    int to, cnt; // to: 인접한 정점, cnt: 남은 사용 횟수
    Edge *dual; // dual: 역방향 간선을 가리키는 포인터
    Edge(): Edge(-1, 0){}
    Edge(int to1, int cnt1): to(to1), cnt(cnt1), dual(nullptr){}
};

int N, degree[1000];
vector<Edge*> adj[1000];
bool visited[1000];

// 컴포넌트별로 방문하는 dfs
int dfs(int curr){
    int result = 1;
    visited[curr] = true;
    for(Edge* e: adj[curr]){
        int next = e->to;
        if(!visited[next]) result += dfs(next);
    }
    return result;
}

// 오일러 회로를 출력하는 dfs
void Eulerian(int curr){
    for(Edge *e: adj[curr]){
        if(e->cnt > 0){
            // 순방향, 역방향 간선을 하나씩 지움
            e->cnt--;
            e->dual->cnt--;
            // dfs
            Eulerian(e->to);
        }
    }
    printf("%d ", curr+1);
}



int main(){
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            int val;
            scanf("%d", &val);
            // 간선 추가
            if(j > i && val > 0){
                Edge *e1 = new Edge(j, val), *e2 = new Edge(i, val);
                e1->dual = e2;
                e2->dual = e1;
                adj[i].push_back(e1);
                adj[j].push_back(e2);
                degree[i] += val;
                degree[j] += val;
            }
        }
    }
    // 차수가 홀수인 정점이 존재하면 불가능
    for(int i=0; i<N; i++){
        if(degree[i]%2 == 1){
            puts("-1");
            return 0;
        }
    }

    bool flag = false;
    int start = -1;
    for(int i=0; i<N; i++){
        if(!visited[i]){
            int cSize = dfs(i);
            if(cSize > 1){
                if(flag){ // 크기가 2 이상인 컴포넌트가 2개 이상이면 불가능
                    puts("-1");
                    return 0;
                }
                else{
                    start = i;
                    flag = true;
                }
            }
        }
    }
    if(start == -1) start = 0;

    // 오일러 회로 찾기 시작
    Eulerian(start);
}

그냥 오일러 회로 하나만 찍으라는 비교적 간단한 문제인데 할 건 더럽게 많습니다.

오일러 회로가 아니라 오일러 경로를 찾아야 하는 문제의 경우, 즉 명확히 시작점과 끝점이 달라야 하는 경우, 차수가 홀수인 정점이 정확히 2개가 존재해야 합니다.

저걸 먼저 체크한 후, 두 홀수차수 정점 사이에 가상의 간선을 한 개 만든 후 오일러 회로를 찾은 뒤에 가상간선을 삭제하면 나머지가 오일러 경로가 됩니다.

또, 방향 그래프에서도 오일러 회로를 찾을 수 있는데 이때는 각 정점마다 indegree와 outdegree가 같아야 회로가 존재합니다. 이후는 비슷하게 하면 됩니다. 단, 위와 같이 재귀 호출이 끝나는 시점에 자신을 경로의 맨 끝에 붙이는 방식을 사용할 경우, 마지막에 경로 전체를 뒤집어 줘야 합니다.

오일러 회로나 경로는 정말 보기 힘든 문제인데, 주로 딱 보고 이게 오일러 회로 문제라는 걸 알 수가 없습니다. 나오는 족족 상당히 기상천외하고 신박한 발상을 요구합니다.

그 때문에 추천 문제의 목록 자체가 상당한 스포일러가 됩니다. 이 문제들은 오일러 회로와 엮여있음을 아는 순간 거의 90%는 도달한 것인 동시에, 엄청난 스포가 맞죠.

오일러 회로 관련 문제

1199번: 오일러 회로

위에서 설명한 문제입니다.

1616번: 드럼통 굴리기 (★)

갓문제 1. 문제를 다르게 표현하면 모든 M자리 K진수를 한 개씩 만드는 겁니다. (M-1)자리의 모든 K진수 K^(M-1)개가 각 정점입니다. 이제 정점 u에서 0~K-1 사이의 모든 수 k에 대해, u의 첫 한 자리를 지우고 마지막에 k를 붙여 새로 만들어진 M-1자리 K진수수 v로 가는 간선을 만들고 각각 k라 마킹합니다. 총 간선 수는 K^(M-1)*K = K^M개입니다. 이제 여기서 오일러 회로를 찾는 것이 곧 문제를 푸는 셈이 되겠죠!

단, 제한이 너무 빡빡하기 때문에 시간이든 메모리든 초과가 엄청나게 일어납니다. 최대한 정적 배열로 해결해야 합니다. 또한, M자리 K진수가 K^M개 있는 것은 맞고 각각 십진법으로 나타낼 시 0~K^M-1로 일대일 대응되는 것도 맞지만, 그냥 보이는 그대로 문자열로 저장한다던가 하면 오버헤드가 클 수 있습니다. 특히 5백만 자리 2진수 같은 걸 저장했다간...

1591번: 수열 복원 (★)

갓문제 2. 위의 드럼통 굴리기 문제와 유사합니다. 주어진 길이 M의 부분수열들마다, 2개의 길이 M-1인 부분수열이 중복 상관없이 등장하게 되는데, 이러한 각 부분수열을 정점으로 둡니다. 이때는 값 자체가 같으면 같은 정점입니다. 이제 i번째 M자리 부분수열에서 마지막 항을 제거한 부분수열 -> 첫 항을 제거한 부분수열로 가는 간선을 추가해 주고, 단방향 오일러 경로를 찾으면 됩니다.

역시 중복 간선이 존재할 수 있으니 주의해야 합니다. 또한 답이 회로일 수도, 아닐 수도 있으므로 주의해야 합니다.

참조
https://blog.naver.com/kks227