[백준] 1199 오일러 회로💫

⚡백준 1199 오일러 회로

• https://www.acmicpc.net/problem/1199

• 오일러 회로 출력하는 문제

• 입력으로 주어지는 그래프는 모두 연결되어 있다
  -> 모든 간선이 하나의 컴포넌트에 포함되어 있다
  -> 그래프의 연결 요소(컴포넌트)의 개수를 세지 않아도 된다

• 53% 시간 초과

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int N;
int cnt[1001] = { 0 };
int adj[1001][1001] = { 0 };

void getEulerCircuit(int here) {

	for (int i = 0; i< N; ++i) {
		while (adj[here][i] > 0) {
			adj[here][i]--;
			adj[i][here]--;

			getEulerCircuit(i);
		}
	}
	cout << here + 1<<" ";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> adj[i][j];
			cnt[i] += adj[i][j];
		}
		if (cnt[i] % 2) {
			cout << -1;
			return 0;
		}
	}
	
	//오일러 서킷 구하기
	getEulerCircuit(0);
	return 0;
}

📌 참고자료

• 오일러 서킷, 오일러 경로
  https://coloredrabbit.tistory.com/36