[백준 1199] 오일러 회로

• 문제 : 1199 오일러 회로

• 유형 : 백트래킹

• 아이디어 : 오일러 회로가 되기 위해서는 한 노드에서 간선의 개수가 짝수인 것들만 있어야 하기때문에 노드에 간선이 홀수개 연결되어 있으면 불가능한 경우로 판단한다. 오일러 회로라는 것이 판단되면 어느 노드에서 시작하더라도 시작점으로 돌아올 수 있기 때문에 1번 노드를 시작으로 전체 간선을 순회할 때까지 dfs를 반복한다.

• 풀이 : 먼저 전체 간선의 개수를 구하기 위해서 간선의 시작점이 도착점 보다 작은 것들을 전부 카운트하여 저장한다. 그리고 각 노드마다 연결된 간선의 개수가 홀수이면 카운트하여 만약 카운트된 것이 있다면 -1을 출력한다. 모든 노드에 연결된 간선이 짝수개이면 1번노드를 시작으로 순회를 시작한다. 깊이가 간선개수와 동일할 때까지 백트레킹하면서 순회하고 한단계 들어갈때마다 경로를 저장해둔다.

• 코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int n, m, last, c;
int arr[1001][1001];
int path[1000001];

bool Euler(int now, int d) {
	path[d] = now;

	if (d == m) {
		for (int i = 0; i <= m; i++) cout << path[i] + 1 << ' ';
		return true;
	}

	for (int i = 0; i < n; i++) {
		if (arr[now][i]) {
			arr[now][i]--;
			arr[i][now]--;

			if (Euler(i, d + 1)) return true;

			arr[now][i]++;
			arr[i][now]++;
		}
	}
	return false;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (i < j && arr[i][j]) m += arr[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		int s = 0;
		for (int j = 0; j < n; j++) s += arr[i][j];
		if (s % 2 == 1) c++;
	}

	if (c == 0) Euler(0, 0);
	else cout << -1;

	return 0;
}