오일러 경로?

오일러 경로를 구하는 알고리즘은 다음과 같다.

void dfs(int now){
	for(int nxt=1; nxt<=n; nxt++){
		if(g[now][nxt] > 0){
			g[now][nxt]--;
			g[nxt][now]--;
			dfs(nxt);
		}
	}
	printf("%d ", now);
}

 

나는 이 코드와 알고리즘에 대한 설명을 읽고 이해를 할 수 없었다. "dfs하면서 사이클을 찾으면 끼워 넣는다"로 보통 설명하는 것 같은데, 어떤 사고를 거치면 저런 코드가 나오는 것일까? 이에 대해 오랜 시간 고민해봤지만 아직도 잘 모르겠다.

 

그래도 다행인 점은 적어도 내가 납득할 수 있는 설명을 찾았다는 것이다. dfs(now)를 호출하면 현재 그래프에 남아있는 간선을 사용해서 now로 끝나는 오일러 경로를 출력하게 된다. 정확히는, 기존에 출력했던 경로 뒤에 now로 끝나는 오일러 경로가 추가로 출력되며, 이렇게 만들어진 오일러 경로는 now로 끝나는 valid한 경로다.

 

dfs(now)에서 dfs(nxt)를 호출하게 되면 두 가지 케이스가 있다. 첫 번째는 now -> nxt 간선이 단절선이 아닌 경우다. 이 경우는 nxt로 끝나는 오일러 경로를 만들고 nxt -> now를 추가하면 now로 끝나는 오일러 경로가 된다. 두 번째는 단절선인 경우다. 이 경우에는 nxt 쪽 컴포넌트를 순회하는 오일러 경로를 만들고(첫번째 재귀호출) nxt -> now가 추가되고, now쪽 컴포넌트를 순회하는 오일러 경로를 만들게 된다(두번째 재귀호출). 착각하면 안 되는 점은 nxt -> now 간선이 추가되는 시점이 우리가 분석하고 있는 dfs(now)가 리턴되는 시점이 아니라 dfs(now)에서 재귀적으로 호출된 다른 dfs(now)에서 추가된다는 것이다.

 

따라서, dfs 함수에서 dfs를 재귀호출하는 횟수는 2회 이하임을 알 수 있다. "dfs하면서 사이클을 찾으면 끼워 넣는다"라는 설명은 아마 두 번째 케이스에서 오일러 경로가 구성되는 방식을 설명하는 말인 것 같다.

 

유향 그래프의 경우도 비슷한 논리로 분석할 수 있다. 주의해야할 점은 nxt -> now 형태로 간선을 추가하기 때문에 dfs함수에서 탐색하는 인접리스트는 간선의 방향이 뒤집힌 형태로 있어야 한다는 것이다.

 

대충 이 정도 직관만 있으면 정당성 증명이 가능할 것이라고 생각했는데, 생각처럼 잘 되지는 않았다. 그래도 코드가 어떤 방식으로 돌아가는지 이해하기에는 충분하다고 생각한다. 나중에 엄밀한 증명을 알게 된다면 공유하겠다.