[백준] 오일러 회로

유의할점

간선이 여러개 있을 수있다.

무향 그래프 == 양방향 그래프

adj → 그래프를 표현하는 변수로 사용

오일러 회로의 함정 : 간선이 없다면 정점이 서로 떨어져있어도 오일러 회로가 존재한다.

풀이

check 함수 : 모든 정점에 인접한 간선의 수가 짝수인지 확인한다. 이때 두 정점사이의 간선의 수가 0이상 10이하임에 주의 한다. (실수한 부분 : 1이라고 생각함)

makePath 함수 : 오일러 서킷을 만든다. 간단하다. 한 정점에 대해서 DFS를 실행하고, 방문할 수 있는 정점이 없는 경우 해당 정점을 서킷에 push한다.

만약 방향 그래프였을경우 만들어진 서킷을 reverse했어야했다. 또한 들어오는 간선의 수와 나가는 간선의 수가 동일한지 확인했어야한다.

코드

C++

//adj : 그래프 표현
#include <iostream>
#include <vector>

using namespace std;
int N;

/*
오일러 회로인 경우 dfs이용해서 경로생성
*/
vector <int> path;

void makePath(int here, vector<vector<int>>& adj) {
	for (int there = 0; there < N; there++) {
		if (adj[here][there]) {
			adj[here][there]--;
			adj[there][here]--;
			makePath(there, adj);
		}
	}
	path.push_back(here);
	return;
}

/*
오일러 회로인지 아닌지 체크하는 함수.
*/
bool check(vector<vector<int>>& adj) {
	for (int y = 0; y < N; y++) {
		int eo = 0;
		for (int x = 0; x < N; x++)
			if (adj[y][x]) eo += adj[y][x];
		if (eo % 2)
			return false;
	}
	return true;
}

int main() {
	cin >> N;
	vector<vector<int>> adj(N, vector<int>(N, 0));
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			cin >> adj[y][x];
	if (!check(adj)) {
		cout << "-1";
		return 0;
	}
	makePath(0, adj);
	for (int v : path)
		cout << v + 1 << " ";
}