문제 개요

주어진 그래프에서 시작 정점 1에서 출발하여 모든 간선을 정방향과 역방향으로 정확히 한 번씩 지나가며, 다시 1로 돌아오는 경로를 찾는 문제이다. 이는 양방향 그래프 내에서 오일러 회로를 구성하는 전형적인 예시이다.

접근 방법

모든 간선이 두 번(정방향/역방향) 방문되며, 시작과 끝이 동일한 특성은 오일러 회로의 조건을 만족한다. 따라서 깊이 우선 탐색 기반의 회로 탐색이 가능하다. 두 가지 구현 방식을 비교할 수 있다:

• 스택 기반 반복 구현: 현재 정점에서 연결된 간선 중 아직 사용되지 않은 것을 선택해 스택에 추가하고, 더 이상 진행 불가능하면 결과 배열에 정점 추가.
• 재귀 기반 탐색: 현재 정점에서 미사용 간선을 순회하며 재귀 호출 후, 해당 정점을 출력함으로써 후위 순서로 경로 생성.

구현 코드 (스택 기반)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 50007;
const int maxe = 100000;

int n, m, u, v, tot, top, t;
int head[maxn], stc[maxe], ans[maxe], vis[maxe];

struct Edge {
    int v, next;
} ed[maxe];

void addEdge(int u, int v) {
    ed[tot].v = v;
    ed[tot].next = head[u];
    head[u] = tot++;

    ed[tot].v = u;
    ed[tot].next = head[v];
    head[v] = tot++;
}

void eulerTour() {
    stc[++top] = 1;
    while (top > 0) {
        int x = stc[top];
        int& i = head[x];
        while (i != -1 && vis[i]) i = ed[i].next;
        if (i != -1) {
            stc[++top] = ed[i].v;
            head[x] = ed[i].next;
            vis[i] = 1;
        } else {
            top--;
            ans[++t] = x;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    tot = top = t = 0;
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }

    eulerTour();
    for (int i = t; i >= 1; --i)
        printf("%d\n", ans[i]);
    return 0;
}

구현 코드 (재귀 기반)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 10007;
const int maxe = 20000;

int n, m, u, v, tot;
int head[maxn], vis[maxe];

struct Edge {
    int v, next;
} ed[maxe];

void addEdge(int u, int v) {
    ed[tot].v = v;
    ed[tot].next = head[u];
    head[u] = tot++;

    ed[tot].v = u;
    ed[tot].next = head[v];
    head[v] = tot++;
}

void dfs(int x) {
    for (int i = head[x]; i != -1; i = ed[i].next) {
        if (!vis[i]) {
            vis[i] = 1;
            dfs(ed[i].v);
        }
    }
    printf("%d\n", x);
}

int main() {
    scanf("%d%d", &n, &m);
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }

    dfs(1);
    return 0;
}

성능 차이 분석

스택 기반 구현은 반복 구조로 인해 함수 호출 오버헤드가 적으며, 메모리 접근도 더 효율적이다. 반면 재귀 구현은 깊이 탐색 시 스택 프레임 관리가 필요해 성능 저하가 발생할 수 있다. 실제 테스트에서는 스택 버전이 약 1초 가량 빠른 것으로 나타났다.