[그래프] 오일러 회로

오일러 회로란?

오일러 회로란, 그래프의 모든 간선을 한 번씩만 통과해서, 시작점으로 돌아오는 사이클을 말합니다. 한붓 그리기와 유사한 개념입니다.
오일러 회로가 되기 위해서는 그래프가 단 하나의 컴포넌트로 구성이 되어있어야 하며, 모든 정점의 차수는 짝수가 되어야 합니다.
만약 차수가 홀수인 정점이 두 개 있다면, 오일러 경로를 구할 수 있습니다.

회로는 시작 정점으로 다시 돌아와야 하고, 경로는 시작 정점으로 돌아오지 않아도 됩니다.

작동 방식

오일러 회로를 구하는 방법을 알아봅시다.

임의의 정점 V를 잡고 dfs를 돌려서 V로 다시 돌아오는 사이클을 찾습니다. 그 경로를 P라고 합시다.
그래프의 모든 정점을 탐색하지 않았다면, P에서 탐색하지 않은 간선이 있는 정점 V’를 찾아 해당 정점부터 dfs를 다시 돌립니다. 그 경로를 P’라고 합시다.
P와 P’를 합칩니다.
그래프 상에 있는 모든 정점을 탐색할 때까지 2, 3번을 반복합니다.

작동 과정

글만 봐서는 이해가 잘 안되기 때문에 예시 그래프를 가져오겠습니다.

위 그래프에서 오일러 회로를 찾아봅시다.

먼저 1번 정점에서 시작해 다시 1번 정점으로 돌아오는 사이클 중, 아무거나 하나를 고릅시다. 저는 1 3 7 4 1을 고르겠습니다.

현재 경로는 (1 3 7 4 1)입니다.

"1" 3 7 4 1에서 1로 시작하는 사이클이 없기 때문에 그 다음 1 "3" 7 4 1 3으로 시작하는 사이클인 3 2 8 6 9 3 을 고르겠습니다.

이전 경로인 1 "3" 7 4 1 에서 3이 있는 자리에 이번 단계에서 찾은 사이클을 집어넣어줍시다.
현재 경로는 1 (3 2 8 6 9 3) 7 4 1입니다.

1 3 "2" 8 6 9 3 7 4 1에서 2로 시작하는 사이클이 없기 때문에 그 다음 1 3 2 "8" 6 9 3 7 4 1 8로 시작하는 사이클인 8 12 9 8을 고르겠습니다.

이전 경로인 1 3 2 "8" 6 9 3 7 4 1 에서 8이 있는 자리에 이번 단계에서 찾은 사이클을 삽입합니다.
현재 경로는 1 3 2 (8 12 9 8) 6 9 3 7 4 1입니다.

같은 방식으로 12로 시작하는 사이클 12 13 14 12을 찾은 뒤, 이전 경로와 병합합니다. 1 3 2 8 (12 13 14 12) 9 8 6 9 3 7 4 1

그 다음으로는 13 9 7 10 13과 10 4 5 11 10을 차례로 찾은 뒤, 이전 경로와 병합해줍니다. 그러면 1 3 2 8 12 13 9 7 10 4 5 11 10 13 14 12 9 8 6 9 3 7 4 1 와 같이 됩니다.

모든 간선을 다 탐색했으므로 탐색을 종료합니다.

구현 방법

BOJ1199번 “오일러 회로” 문제를 코드로 구현해봅시다.

가장 먼저, 변수를 몇 개 정의합시다.

n은 정점의 개수입니다.
g는 인접 행렬입니다.
start는 오일러회로의 시작점을 저장합니다.

모든 정점의 차수가 짝수인지 구해봅시다.
만약 아직 start가 정해지지 않았고, 현재 정점의 차수가 1 이상이라면 그 정점을 start에 저장해 오일러 회로의 시작점이라는 것을 명시해줍니다.

bool chk(){
	for(int i=1; i<=n; i++){
		int cnt = 0;
		for(int j=1; j<=n; j++){
			cnt += g[i][j];
		}
		if(cnt&1) return 0;
		if(start == 0 && cnt > 0) start = i;
	}
	return 1;
}

오일러 회로를 찾는 dfs탐색을 구현합니다.

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);
}