Euler Path & Circuit
Prerequisite
- DFS
Eulerian Path & Cycle
오일러 경로 (Eulerian Path)는 다음과 같다.
그래프에서 시작점 $s$ 에서 출발하여 모든 간선을 한 번씩 거치고 끝점 $e$로 도달하는 경로
이 때, ${\color{salmon} s=e }$ 이면 오일러 회로 (Eulerian Circuit) 이라 부른다.
오일러 회로는 연결 그래프라면, 어떤 정점에서 시작해도 모든 경로를 거치고 자기 자신으로 돌아올 수 있다.
주의할 점은, 꼭 연결 그래프가 아니더라도 오일러 경회로라고 부를 수 있다는 것이다. 어떤 정점이 다른 정점들과 하나의 간선도 없이 떨어져 있으면 연결 그래프가 아니지만, 방문할 간선이 없기 때문에 문제가 없다.
오일러 경회로는 문제에 가끔 등장하지만, 이게 오일러 경회로를 쓰는건지 뭔지 알지도 못한채로 폭사당할 정도의 난이도를 자랑하는 문제들이 대부분이며, 그저 개념적으로 증명에만 쓰일 수도 있다.
조건
오일러 회로
오일러 회로가 될 수 있는 조건은 다음과 같다.
무방향 간선일 때
모든 정점에서 간선의 수가 짝수이기만 하면 된다.
만약 어떤 정점에서 간선의 수가 홀수라면 그 정점으로 나갔으면 다시 그 정점으로 못돌아오기 때문이다.
유방향 간선일 때
모든 정점에서 나가는 간선과 들어오는 간선의 개수가 같아야 한다.
즉, 연결된 간선들의 개수의 합은 (나가는 간선 + 들어오는 간선) 짝수가 된다.
오일러 경로
오일러 경로가 될 수 있는 조건은 다음과 같다.
무방향 간선일 때
두 정점에서만 간선의 수가 홀수이고 나머지 정점들에서의 간선의 수는 짝수이면 된다.
둘 중 아무 정점에서 출발해도 나머지 정점으로 도착하는 두 개의 경로가 나올 수 있다.
유방향 간선일 때
시작점과 끝점을 제외한 모든 정점에서 나가는 간선과 들어오는 간선의 개수가 같다.
시작점은 나가는 간선이 들어오는 간선보다 1개 많고, 끝점은 들어오는 간선이 나가는 간선보다 1개 많다.
구현
구현엔 주로 DFS와 비슷한 방식의 재귀함수가 쓰인다.
이를 Hierholzer’s Algorithm 이라 한다. 시간 복잡도는 $O(E)$ 이다.
알고리즘은 대략 다음과 같다.
임의의 정점 $v$ 에서 그 정점에서 다시 $v$로 돌아오는 그래프 탐색을 한다.
만약 싸이클을 찾아 $v$ 로 다시 돌아왔어도 미사용된 간선이 있음을 알 수 있다.
간선을 빠짐없이 포함하는 경로를 구성하는 방법은, $v \to \cdots u \cdots \to v$ 라는 경로가 있을 때, $u$ 에서 사용되지 않은 간선을 다시 사용해 $u$ 로의 싸이클을 경로에 포함시켜주는 방식이다.
어떤 정점 $v$ 에 도달하면 자신이 미사용한 간선이 없을 때 까지 간선을 모두 소모해준 후, $v$ 를 방문했다고 표기를 해야한다.
그렇게 만들어진 결과는 원래의 경회로 방문 순서를 뒤집은 결과이기 때문에 유방향 그래프라면 결과를 뒤집는 등 후처리가 필요하다.
이런식으로 구현을 하기 위해서 사용한 간선을 지워주는 테크닉이 필요한데, $e[u][v]$ 가 $u \to v$ 로 가는 남은 간선의 수라고 할 때, $u \to v$ 를 사용하면 $e[u][v] \coloneqq e[u][v] - 1$ 과 같이 계속 업데이트 해주면서 사용해줄 수 있다.
무방향 그래프에서는 $u \to v$ 를 하나 사용했다면 $v \to u$ 도 하나를 사용한 처리를 해주어야 하는데, 만약 구조체같은걸 써서 구현을 할경우, $u$ 에서 나가는 간선과 짝이 되는 $v$ 의 간선의 카운팅도 -1를 해주어야된다.
이것은 포인터를 이용해 기록해두거나 $v$ 의 간선들 중 $v - u$ 간선이 몇 번째 인덱스인지 $u-v$ 간선에 기록해두는 것으로 구현할 수 있다.
다 쓴 간선을 빼주기 위해 $e[u]$ 의 리스트들을 마지막부터 보다가 $e[u][last]=0$ 이 되었다면 pop_back 을 해주는 방식으로 최적화가 가능하다.
DFS를 재귀로 돌리는 것과 스택으로 돌리는 것은 완전히 같은것이 아니며, 방문 순서를 기록하거나 순서를 다룸에 있어서 스택을 쓰면 좀 더 직관적인 방법으로 구현이 어렵기 때문에 오일러 경회로는 재귀로 구현해줌이 간편하다.
무방향 그래프에서의 오일러 회로를 구현하는 문제인데, 정확히 제대로 구현해야 통과할 수 있다.
모든 최적화가 안된 코드들을 다 무자비하게 터뜨려버리는 테스트 케이스가 추가되어서 정답률이 극악이 되었고 난이도도 높아졌다.
void fail() {
cout << -1;
exit(0);
}
void solve() {
int n;
cin >> n;
vector<vector<array<int, 3>>> edges(n);
vi in(n), out(n);
for (int i = 0; i < n; i++) {
for (int j = 0, k; j < n; j++) {
cin >> k;
in[j] += k;
out[i] += k;
if (k && j > i) {
edges[i].pb({j, k, sz(edges[j])});
edges[j].pb({i, k, sz(edges[i]) - 1});
}
}
}
// 모든 정점의 간선의 개수가 짝수가 아니라면 fail
for (int i = 0; i < n; i++) {
assert(in[i] == out[i]);
if (in[i] % 2) fail();
}
function<void(int)> fn = [&](int cur) -> void {
while (sz(edges[cur])) {
if (!edges[cur].back()[1]) {
edges[cur].pop_back();
continue;
}
int to = edges[cur].back()[0];
int to_edge_idx = edges[cur].back()[2];
edges[to][to_edge_idx][1]--;
edges[cur].back()[1]--;
fn(to);
}
cout << cur + 1 << ' ';
};
fn(0);
}
연습 문제
위 문제이다.
무방향 그래프의 오일러 경로 문제이다.
만약 회로의 조건을 충족한다면 정답은 1이다.
무방향 그래프에서 오일러 경로가 되기 위한 조건은 모든 정점의 간선의 개수가 짝수개이고 두 정점만 홀수개이므로 조건을 충족시키기 위해 간선을 추가해주는 방식을 이용할 수 있다.
따라서 정답은 그래프를 각각 연결 그래프로 끊어서 $max(1, \dfrac {\text{홀수 정점의 개수}}2 )$ 이다.
연결 그래프에서 간선의 개수가 홀수인 정점이 홀수개가 될 수 없다.
악수 정리에 의해 모든 정점이 가진 간선의 개수는 $2E$ 인데, 이건 짝수라서 홀수인 정점이 홀수개가 되면 짝수가 될 수 없어 모순이다.
Comments