(라이님 블로그 대회 알고리즘 따라잡기 21) 오일러 회로(Eulerian Circuit)

오늘은 오일러 회로를 공부해보았다. Eulerian이라고 쓰는게 맞는 표현인지 오늘 처음 알았다ㅎㅎ...

 

늘 그렇듯 오늘도 라이님 블로그를 참고했다. 

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220800097205&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

오일러 경로(Eulerian Path), 오일러 회로(Eulerian Circuit) (수정: 2019-08-20)

 

여기 있는 코드는 gpt와 조금 수정해보았다. 아무래도 동적 할당(?)을 자동으로 해주는 vector가 편해서 그런지 gpt 코드가 더 편하다!

 

참고로 vector에서 resize와 reserve의 차이점은 초기화 유무에 있다!

아래 블로그를 참고!!

https://hoondev.tistory.com/7

[C++] vector의 reserve()로 push_back() 시간을 줄이자!

 

보통 나의 경우 효율성을 위해 vector의 크기를 정의해주므로 reserve를 쓰는게 더 적절해보인다!

(수정 : 24.7.1. 아래 코드는 reserve를 쓰면 안 돌아간다. ㅎㅎ

 

reserve는 벡터의 용량(capacity)을 확보해놓을 뿐 길이를 늘리는게 아니다!!!

그래서 adj[i]를 부르면 adj의 i번째 자리를 확보해놓았을 뿐 만들지 않았기 때문에 에러가 발생한다)

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// Edge(도착점, 간선 갯수)
struct Edge {
	int to, cnt; 
	Edge(int to, int cnt) : to(to), cnt(cnt) {}
};

int N;
vector<vector<Edge>> adj;

// 만약 홀수인 정점이 존재한다면 오일러 회로는 존재하지 않음 
bool CheckEulerianCircuit() {
	vector<int> degree(N, 0);
	for (int i = 0; i < N; i++) {
		for (const Edge& e : adj[i]) {
			degree[i] += e.cnt;
		}
		if (degree[i] % 2 != 0) return false;
	}
	return true;
}

// EulerianCircuit을 Hierholzer's Algorithm을 사용해 푸는 알고리즘
void EulerianCircuit(int start) {
	vector<int> idx(N, 0);
	vector<int> circuit;
	stack<int> st;

	st.push(start);
	while (!st.empty()) {
		int u = st.top();

		// 만약 u의 index가 u와 연결된 정점들의 갯수보다 작고
		// u와 연결된 idx[u]번째 정점과 u가 연결되어 있지 않다면
		// idx[u]를 늘린다

		while (idx[u] < adj[u].size() && adj[u][idx[u]].cnt == 0) idx[u]++;


		// u와 연결된 정점들을 모두 사용했다면
		if (idx[u]== adj[u].size()) {
			circuit.push_back(u);
			st.pop();
		}
		// u와 연결된 idx[u]번째 정점과 u가 연결되어 있다면
		else {
			Edge& e = adj[u][idx[u]];
			--e.cnt;
			for (Edge& re : adj[e.to]) {
				if (re.to == u) { re.cnt--; break; }
			}
			st.push(e.to);
		}
	}
	for (vector<int>::reverse_iterator it = circuit.rbegin(); it < circuit.rend(); it++) cout << (*it + 1) << "\n";

	return;
}

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

	 cin >> N;
	 adj.resize(N);
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int val; cin >> val;
			if (i > j && val != 0) {
				adj[i].push_back({ j, val });
				adj[j].push_back({ i, val });
			}
		}
	}

	if (!CheckEulerianCircuit()) {
		cout << "-1";
		return 0;
	}
	else {
		for (int i = 0; i < N; i++) {
			if (!adj[i].empty()) {
				EulerianCircuit(i);
				break;
			}
		}
	}

	return 0;
}