오일러 경로는 이름만 보고 판단하면 핵심을 놓치기 쉬운 주제입니다. 이 글은 최신 출처와 구조를 기준으로 독자가 실제로 확인해야 할 기준을 정리합니다.
핵심은 모든 간선을 한 번씩 쓰는 오일러 경로와 회로 조건 이해입니다. 단정적인 결론보다 확인 순서와 리스크를 분리해 보는 것이 중요합니다.
오일러 경로 흐름을 그림으로 보기
오일러 경로는 정점보다 간선을 보는 문제다
오일러 경로는 그래프의 모든 간선을 정확히 한 번씩 사용하는 경로입니다. 여기서 중요한 것은 모든 정점을 한 번씩 방문하는 것이 아니라 모든 간선을 한 번씩 쓰는 것입니다.
핵심은 정점 방문 문제가 아니라 간선 사용 문제라는 점입니다.
오일러 경로와 오일러 회로 차이
- 오일러 경로: 모든 간선을 한 번씩 쓰되 시작점과 끝점이 달라도 된다
- 오일러 회로: 모든 간선을 한 번씩 쓰고 시작점으로 다시 돌아온다
- 해밀턴 경로: 모든 정점을 한 번씩 방문하는 문제라서 기준이 다르다
이 차이를 놓치면 문제를 완전히 다르게 풀게 됩니다. 간선이 핵심이면 오일러를 의심하고, 정점 방문이 핵심이면 해밀턴이나 백트래킹 성격을 먼저 봐야 합니다.
무방향 그래프에서 조건을 먼저 보자
무방향 그래프에서는 차수가 핵심입니다. 연결된 그래프라는 전제를 두면, 모든 정점의 차수가 짝수이면 오일러 회로가 가능합니다. 홀수 차수 정점이 정확히 2개이면 오일러 경로가 가능합니다.
- 홀수 차수 정점이 0개이면 오일러 회로 가능
- 홀수 차수 정점이 2개이면 오일러 경로 가능
- 홀수 차수 정점이 그 외 개수이면 불가능
왜 홀수 차수가 중요할까
중간 정점에서는 들어온 간선이 있으면 나가는 간선도 필요합니다. 그래서 대부분의 정점은 간선이 짝으로 맞아야 합니다.
시작점과 끝점만 예외가 될 수 있습니다. 시작점은 나가는 간선이 하나 더 많을 수 있고, 끝점은 들어오는 간선이 하나 더 많을 수 있습니다. 무방향 그래프에서는 이것이 홀수 차수 정점 2개로 나타납니다.
Hierholzer 알고리즘 감각
Hierholzer 알고리즘은 갈 수 있는 간선을 따라가며 사용 처리하고, 더 이상 갈 곳이 없을 때 경로에 정점을 넣는 방식으로 작동합니다. DFS 후위 처리와 비슷한 감각이 있습니다.
vector<vector<pair>> g;
vector used;
vector path;
void dfs(int v) {
while (!g[v].empty()) {
auto [nxt, edgeId] = g[v].back();
g[v].pop_back();
if (used[edgeId]) continue;
used[edgeId] = 1;
dfs(nxt);
}
path.push_back(v);
}
// dfs(start) 이후 path를 뒤집으면 오일러 경로 후보가 된다.문제에서 오일러를 떠올리는 신호
- 모든 길, 모든 티켓, 모든 간선을 한 번씩 써야 한다
- 경로를 실제로 출력해야 한다
- 시작점과 끝점 조건이 차수와 연결된다
- 정점을 여러 번 방문해도 된다는 조건이 있다
정리
오일러 경로와 오일러 회로는 그래프에서 모든 간선을 한 번씩 쓰는 문제입니다. 정점이 아니라 간선이 중심이라는 점만 잡아도 해밀턴 문제와 헷갈릴 가능성이 줄어듭니다. 조건 판별은 차수로 시작하고, 실제 경로 구성은 Hierholzer 알고리즘으로 이어가면 됩니다.
관련 글로는 DFS와 BFS 차이, 그래프 입력 인접 리스트와 인접 행렬, SCC 알고리즘을 함께 보면 좋습니다. 외부 기준은 cp-algorithms – Eulerian Path, Wikipedia – Eulerian path을 확인했습니다.
